【PA2019】Trzy Kule
组合计数，前缀和。
题目大意：
给定三个长度为 $n$ 的 01 串 $s_1,s_2,s_3$。
问有多少个长度为 $n$ 的 01 串 $s’$ 至少满足下列三个条件中的一个：
- $\sum\limits_{i=1}^n |s_{1,i}-s’_i|\leq t_1$
- $\sum\limits_{i=1}^n |s_{2,i}-s’_i|\leq t_2$
- $\sum\limits_{i=1}^n |s_{3,i}-s’_i|\leq t_3$
题解：
我们可以先把 $s_1$ 变为全 $1$，$s_2$ 和 $s_3$ 进行变换使得每一位都对应即可。
总的字符串个数是 $2^n$，我们考虑求出以上三个条件都不满足的串的个数。
我们考虑每个位，由于 $s_1$ 已经是全 $1$，那么三个字符串的这个位的情况只有四种：100，101，110，111。设它们的出现次数分别为 $a_1,a_2,a_3,a_4$。
我们考虑枚举 110 和 111 的出现个数 $i,j$，那么 001 和 000 的出现个数就为 $a_3-i$，$a_4-j$。
这种情况下，第一个字符串和第二个字符串中出现的 $1$ 的个数是一样的，都是 $i+j$，而第三个字符串中出现的 $1$ 的个数为 $i+a_4-j$。
我们设 100 和 101 的出现次数分别为 $x,y$，那么我们需要满足以下三个不等式，才能对不满足条件的串产生贡献。
- $i+j+x+y\gt t_1$
- $i+j+(a_1-x)+(a_2-y)\gt t_2$
- $i+(a_4-j)+(a_1-x)+y\gt t_3$
整理后可得：
- $i+j\gt t_1-x-y$
- $i+j\gt t_2-(a_1-x)-(a_2-y)$
- $i+(a_4-j)\gt t_3-(a_1-x)-y$
可以合并为两个式子 $i+j\gt \max(t_1-x-y,t_2-(a_1-x)-(a_2-y))$，$i-j\gt t_3-(a_1-x)-y-a_4$。
$(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$ 种不同方案。我们需要统计一个矩形区域内的和，这个可以预处理二维前缀和。之后用乘法原理即可计算方案数。
时空复杂度 $O(n^2)$。可能需要卡常。
Code：
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=10005,md=1e9+7;
int t1,t2,t3,_111,_101,_100,_110,n,fac[N],iv[N];
char s1[N],s2[N],s3[N];
inline int pow(int a,int b){
int ret=1;
for(;b;b>>=1,a=(LL)a*a%md)if(b&1)ret=(LL)ret*a%md;
return ret;
}
inline int C(int x,int y){return(LL)fac[x]*iv[y]%md*iv[x-y]%md;}
int D[N][N],ans;
inline void upd(int&a){a+=a>>31&md;}
int main(){
scanf("%d%d%s%d%s%d%s",&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);
for(int i=*fac=1;i<=n;++i)fac[i]=(LL)fac[i-1]*i%md;
iv[n]=pow(fac[n],md-2);
for(int i=n-1;~i;--i)iv[i]=(i+1LL)*iv[i+1]%md;
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)*(LL)C(_111,j))%md;
}
for(int i=_110+_111;~i;--i){
int*X=D[i],*Y=D[i+1];
for(int j=_110+_111-max(i-_111,0);~j;--j)
X[j]=((LL)X[j]+Y[j]+X[j+1]-Y[j+1]+md)%md;
}
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)),LB=t3+1-(j+_100-i);
if(LA<0)LA=0;if(LB<0)LB=0;
ans=(ans+(LL)D[LA][LB]*C(_100,i)%md*C(_101,j))%md;
}
upd(ans=pow(2,n)-ans);
printf("%d\n",ans);
return 0;
}