题解 P5982 【[PA2019]Trzy kule】
mrsrz
·
·
题解
可能更好的体验
我们可以先把 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。
不难发现，可以和一组 $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：
```cpp
#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;
}
```