洛谷P5982 [PA2019] Trzy kule 题解

题目链接：P5982 [PA2019] Trzy kule

题意：

对于两个长度为 $n$ 的 $01$ 串 $a_{1..n},b_{1..n}$ ，定义它们的距离 $d(a,b)=|a_1-b_1|+|a_2-b_2|+…+|a_n-b_n|$ 。

给定三个长度为 $n$ 的 $01$ 串 $s_1,s_2,s_3$ 以及三个非负整数 $r_1,r_2,r_3(0\le r_i\le n)$ ，问有多少个长度为 $n$ 的 $01$ 串 $S$ 满足 $d(S,s_1)\le r_1,d(S,s_2)\le r_2,d(S,s_3)\le r_3$ 这三个不等式中至少有一个成立。

输入格式：

第一行一个正整数 $n$ 。

第二行一个非负整数 $r_1$ ，然后一个长度为 $n$ 的 $01$ 串 $s_1$ 。

第三行一个非负整数 $r_2$ ，然后一个长度为 $n$ 的 $01$ 串 $s_2$ 。

第四行一个非负整数 $r_3$ ，然后一个长度为 $n$ 的 $01$ 串 $s_3$ 。

输出格式：

输出一行一个整数，即满足条件的 $S$ 的数量模 $10^9+7$ 。

数据范围：

对于 $100\%$ 的数据， $1\le n\le 10^4$ 。

条件计数的常见解法：要么容斥，要么寻找更简洁的充要条件。

这道题，其实两者都有所运用。

首先最基本的容斥，考虑计算不满足任何一个等式的串的个数，最后用 $2^n$ 减去它就是答案。

方便起见，我们可以先把 $s_1$ 变为 $\mathtt{111\dots}$ （全为 $\mathtt{1}$ ），并将 $s_2$ 和 $s_3$ 进行变换。

依次考虑每个位。由于我们的变换操作，现在这三个字符串在每位的情况只有 100,101,110,111 四种。

不妨记这四种情况分别有 $a_1,a_2,a_3,a_4$ 种。

我们枚举因 $S$ 导致的 110 和 111 的出现次数 $i,j$ ，则 001 和 000 的出现次数就为 $a_3 - i,~a_4 - j$ 。

此时对应 $s_1$ 和对应 $s_2$ 的串中出现的 $\mathtt{1}$ 的个数是一样的，都是 $i + j$ ，对应 $s_3$ 的串中出现的为 $i + a_4 -j$

设 100 和 101 的出现次数分别为 $x,y$ 。那么我们需要满足以下条件：

$\begin{aligned} & i+j+x+y>t_1 \\[6pt]& i+j+\left(a_1-x\right)+\left(a_2-y\right)>t_2 \\[6pt]& i+\left(a_4-j\right)+\left(a_1-x\right)+y>t_3 \end{aligned}$

整理并合并后可以得到以下不等式：

$\begin{aligned} &i+j>\max \left(t_1-x-y, t_2-\left(a_1-x\right)-\left(a_2-y\right)\right) \\[6pt]&i - j > t_3 - (a_1 - x) - y - a_4 \end{aligned}$

任意 $(i + j, i - j)$ 可以唯一确定一组 $i,j$ 。

显然，可以和任何一组 $x,y$ 产生贡献的 $i,j$ ，其对应的 $(i + j, i - j)$ 都落在一个矩形区域内

那么算法就出来了。枚举 $i,j$ ，其本身有 $\binom{a_3}{i}\binom{a_4}{j}$ 种不同方案，我们把它加到二维平面上的点 $(i+j,i-j)$ 处

接着枚举 $x,y$ ，其本身有 $\binom{a_1}{x}\binom{a_2}{y}$ 种不同方案。接着我们只需统计矩形区域内的和，这一点可以通过预处理。

时间复杂度 $\mathcal{O}(n^2)$

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e4 + 15))

char s1[N],s2[N],s3[N];
int n,t1,t2,t3,_111,_101,_100,_110,res,fac[N],inv[N],D[N][N];
int qpow(int a,int b)
{
    int r = 1;
    while(b) {
        if(b & 1) r = r * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return r;
}
int C(int n, int m)
{
    if(m < 0 || n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> t1 >> (s1 + 1) >> t2 >> (s2 + 1) >> t3 >> (s3 + 1);
    for(int i = 1; i <= n; i++)
    {
        if(s1[i] == s2[i] && s2[i] == s3[i]) ++_111;
        else if(s1[i] == s2[i]) ++_110;
        else if(s1[i] == s3[i]) ++_101;
        else ++_100;
    }
    if(_110 > _101) { swap(_110, _101), swap(t2, t3); }
    if(_110 > _100) { swap(_110, _100), swap(t1, t3); }

    fac[0] = 1;
    for(int i = fac[0] = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % mod;
    for(int i = 0; i <= _110; i++)
        for(int j = 0; j <= _111; j++)
        {
            int A = i + j, B = j + _110 - i;
            D[A][B] = (D[A][B] + C(_110, i) * C(_111, j)) % mod;
        }
    for(int i = _110 + _111; ~i; i--)
    {
        int *X = D[i], *Y = D[i + 1];
        for(int j = _110 + _111 - max(i - _111, 0ll); ~j; j--)
            X[j] = (X[j] + Y[j] + X[j + 1] - Y[j + 1] + mod) % mod;
    }
    for(int i = 0; i <= _100; i++)
        for(int j = 0; j <= _101; j++)
        {
            int LA = max(t1 + 1 - i - j, t2 + 1 - (_100 - i) - (_101 - j));
            int LB = t3 + 1 - (j + _100 - i); up(LA, 0); up(LB, 0);
            res = (res + D[LA][LB] * C(_100, i) % mod * C(_101, j)) % mod;
        }
    res = ((qpow(2, n) - res) % mod + mod) % mod;
    cout << res << '\n';
    return 0;
}