洛谷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$ 。那么我们需要满足以下条件：
整理并合并后可以得到以下不等式：
任意 $(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)$
代码：
#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;
}参考文献：
