核桃 OJ 题解 · 化智为空

Linzijian2012 · 2024-08-20 15:11:53 · 个人记录

前言

内容有违反洛谷社区规则的或不规范的，请私信蒟蒻或直接发在评论区。欢迎奆佬们给蒟蒻的题解提出建议！

下文中所有变量均为整数；若有多层括号，则均使用小括号；设 p 为命题，则 p\text{ 为真}\Rightarrow[p]=1，p\text{ 为假}\Rightarrow[p]=0。

正文

1 题目和题意

题目传送门：HT-019-Div.2-S T4 化智为空（emptymind）。

题意：设有 n 维空间，点的坐标为 (x_1,x_2,x_3,\dots,x_n)。设 V=\{(x_1,x_2,\dots,x_n)\,|\,\forall1\le i\le n,x_i\in\{0,1\}\}。现有三个 n 维球，球心分别为 s_1、s_2、s_3（s_i\in V(1\le i\le3)），半径分别为 r_1、r_2、r_3。求 \displaystyle\sum_{P\in V}\bigvee_{i=1}^3\left[\left(\sum_{d=1}^n[s_{i,d}\ne P_d]\right)\leqslant r_i\right]，其中 s_{i,d}、P_d 分别表示 s_i 的第 d 维坐标、P 的第 d 维坐标。结果对 \mathbf{10^9+7} 取模。

数据范围：2\leqslant n\leqslant6\times10^3，0\leqslant r_i\leqslant n-1(1\leqslant i\leqslant3)。

2 解法

注意到：

令 c_t(0\le t\le3) 表示情况“t”的个数，则可以枚举 q_t 表示“当第 d 维的情况为‘t’时，P_d 的总和”（0\le t\le3），那么：

时间复杂度被降到了 O(n^4)。

尝试优化。题目想要的时间复杂度大致是 O(n^2)，所以考虑在知道 q_0 和 q_1 的情况下，统计出合法的 q_2 和 q_3 的个数。这就是解不等式方程：

可以先枚举 q_2 和 q_3，然后用一个二维数组 cnt 记录，每次让 cnt_{q_2-q_3,q_2+q_3}（初始为 0）加上 \binom{c_2}{q_2}\binom{c_3}{q_3}。令：

标红的部分是因为上面的式子中的不等号都是大于号和小于号。式子就变成了：

其中后面的式子可以用二维前缀和 O(1) 求出，所以总时间复杂度 O(n^2)。注意前缀和数组的地址偏移，不要忘了取模。

3 代码

请勿抄题解，后果自负！

AC 链接。

//HT-019-Div.2 D(emptymind)
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 6e3 + 5;
const ll mod = 1e9 + 7;
int n, r[5], s[5][N], c0, c1, c2, c3, shift, limit;
ll fac[N], ivf[N], cnt[N][N << 1], ans;
char S[N];
ll fp(ll x, ll k){
    ll res = 1;
    while (k){
        if (k & 1){
            res = (res * x) % mod;
        }
        x = (x * x) % mod;
        k >>= 1;
    }
    return res;
}
ll C(ll x, ll y){
    if (x < 0 || y < 0 || y > x){
        return 0;
    }
    return ((fac[x] * ivf[x - y]) % mod * ivf[y]) % mod;
}
ll sum(ll X1, ll X2, ll Y1, ll Y2){
    // printf("\tsum(%lld, %lld, %lld, %lld)\n", X1, Y1, X2, Y2);
    X1 += shift;
    Y1 += shift;
    X2 += shift;
    Y2 += shift;// 一、一定要先偏移 
    // printf("X1 : %lld | Y1 : %lld | X2 : %lld | Y2 : %lld\n", X1, Y1, X2, Y2);
    X1 = (X1 < 1 ? 1 : X1);
    X2 = (X2 > c2 + c3 + 1 ? c2 + c3 + 1 : X2);// 这里的上限是 c2 + c3 + 1 而不是 limit 
    Y1 = (Y1 < 1 ? 1 : Y1);
    Y2 = (Y2 > limit ? limit : Y2);// 二、记得限制上下限，防止 RE 
    if (X1 > X2 || Y1 > Y2){
        return 0LL;// 特判，防止 WA 
    }
    ll res = cnt[X2][Y2] - cnt[X1 - 1][Y2] + cnt[X1 - 1][Y1 - 1] - cnt[X2][Y1 - 1];
    return (res % mod + mod) % mod;// 计算前缀和 
}
int main(){
    freopen("emptymind.in", "r", stdin);
    freopen("emptymind.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= 3; i++){
        scanf("\n%d %s", &r[i], S + 1);
        for (int j = 1; j <= n; j++){
            s[i][j] = S[j] ^ 48;
        }
    }
    fac[0] = 1;
    for (int i = 1; i <= n; i++){
        if (s[1][i] + s[2][i] + s[3][i] > 1){
            s[1][i] ^= 1;
            s[2][i] ^= 1;
            s[3][i] ^= 1;
        }
        if (s[1][i] + s[2][i] + s[3][i] == 0){
            c0++;
        }
        c1 += s[3][i];// 注意 c1、c2、c3 的定义 
        c2 += s[2][i];
        c3 += s[1][i];// 同上 
        fac[i] = (fac[i - 1] * i) % mod;
    }
    // printf("%d %d %d %d\n", c0, c1, c2, c3);
    ivf[n] = fp(fac[n], mod - 2);
    for (int i = n; i >= 1; i--){
        ivf[i - 1] = (ivf[i] * i) % mod;
    }
    shift = c3 + 1;// 地址偏移量 
    limit = c2 + c3 + shift;// 前缀和数组第二维的上限 
    for (int q2 = 0; q2 <= c2; q2++){
        for (int q3 = 0; q3 <= c3; q3++){
            ll now = (C(c2, q2) * C(c3, q3)) % mod;
            cnt[q2 - q3 + shift][q2 + q3 + shift] += now;
            cnt[q2 - q3 + shift][q2 + q3 + shift] %= mod;
        }
    }
    /*
    printf("cnt :\n");
    for (int q2 = 0; q2 <= c2; q2++){
        for (int q3 = 0; q3 <= c3; q3++){
            printf("%lld ", cnt[q2 - q3 + shift][q2 + q3 + shift]);
        }
        printf("\n");
    }
//  */
    for (int i = 1; i <= c2 + c3 + 1; i++){
        for (int j = 1; j <= limit; j++){
            cnt[i][j] += cnt[i - 1][j] - cnt[i - 1][j - 1] + cnt[i][j - 1];
            cnt[i][j] = (cnt[i][j] % mod + mod) % mod;
        }
    }// 预处理前缀和 
    for (int q0 = 0; q0 <= c0; q0++){
        for (int q1 = 0; q1 <= c1; q1++){
            int m1 = r[1] - q0 - q1 - c3 + 1;
            int m2 = q0 + q1 + c2 - r[2] - 1;
            int m3 = r[3] - q0 - c1 + q1 + 1;// 同定义 
            ll now = (C(c0, q0) * C(c1, q1)) % mod;
            now = (now * sum(m1, m2, m3, c2 + c3)) % mod;// 注意这里传参的顺序要对应 
            // printf("%d %d %lld\n", q0, q1, now);
            ans = (ans + now) % mod;
        }
    }
    ans = fp(2, n) - ans;// 记得减 
    printf("%lld", (ans % mod + mod) % mod);
    return 0;
}

论蒟蒻调代码的过程：

最开始：评测；样例没过。

Update1：发现前缀和挂了，改完仍然没过样例。新评测。

Update2：发现 c1 和 c3 统计反了，样例输出 11。新评测。

Update3：尝试打 O(n^4) 暴力，结果还 WA 了两个点，第二个大样例没过……暴力代码评测。

Update4：q3 打成 c3 了，改完拿到了暴力应有的 60 分。

Update5：sum 函数传参的时候顺序错了，改完过了第二个大样例。新评测。

Update6：sum 函数内部的 X2 变成了负数，已修正，无 RE 50 分。

Update7：被老师看出来了，X2 的上线是 c2 + c3 + 1，而不是 limit。

附录

蒟蒻其他的核桃 OJ 题解。