QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#69115#1245. Three ballseyiigjknWA 3ms3648kbC++142.1kb2022-12-23 21:06:322022-12-23 21:06:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-23 21:06:33]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3648kb
  • [2022-12-23 21:06:32]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int mod=1e9+7;
int n,fac[10010],finv[10010],sum[10010][10010];
char a[10010],b[10010],c[10010];
inline int add(int x,int y){return (x+=y)<mod?x:x-mod;}
inline void upd(int &x,const int &y){if((x+=y)>=mod) x-=mod;}
inline void upd(int &x,const ll &y){x=(x+y)%mod;}
inline int Binom(int n,int m){return (ll)fac[n]*finv[m]%mod*finv[n-m]%mod;}
int power(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=(ll)a*a%mod)
		if(b&1) ans=(ll)ans*a%mod;
	return ans;
}
int calc(int r1,char *a,int r2,char *b)
{
	int c0=0,c1=0,ans=0;
	static int sum[10010];
	for(int i=1;i<=n;i++) (a[i]==b[i]?c0:c1)++;
	for(int i=0;i<=c1;i++) sum[i]=Binom(c1,i);
	for(int i=1;i<=c1;i++) upd(sum[i],sum[i-1]);
	for(int i=0;i<=c0 && i<=r1 && i<=r2;i++)
	{
		int l=max(c1+i-r2,0),r=min(r1-i,c1);
		if(l>r) break;
		if(l) upd(ans,mod-sum[l-1]);
		upd(ans,sum[r]);
	}
	return ans;
}
int main()
{
	int r1,r2,r3,c1=0,c2=0,c3=0,c4=0,ans=0;
	scanf("%d%d%s%d%s%d%s",&n,&r1,a+1,&r2,b+1,&r3,c+1);
	fac[0]=fac[1]=1;
	for(int i=2;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod;
	finv[n]=power(fac[n],mod-2);
	for(int i=n-1;i>=0;i--) finv[i]=(ll)finv[i+1]*(i+1)%mod;
	for(int i=0;i<=r1;i++) upd(ans,Binom(n,i));
	for(int i=0;i<=r2;i++) upd(ans,Binom(n,i));
	for(int i=0;i<=r3;i++) upd(ans,Binom(n,i));
	upd(ans,mod-calc(r1,a,r2,b));
	upd(ans,mod-calc(r2,b,r3,c));
	upd(ans,mod-calc(r3,c,r1,a));
	for(int i=1;i<=n;i++)
		if(a[i]==b[i] && b[i]==c[i]) c4++;
		else if(b[i]==c[i]) c1++;
		else if(a[i]==c[i]) c2++;
		else if(a[i]==b[i]) c3++;
	for(int i=0;i<=c3;i++)
		for(int j=0;j<=c4;j++)
			sum[i+j][j-i+c3]=(ll)Binom(c3,i)*Binom(c4,j)%mod;
	for(int i=0;i<=c3+c4;i++)
		for(int j=1;j<=c3+c4;j++)
			upd(sum[i][j],sum[i][j-1]);
	for(int i=1;i<=c3+c4;i++)
		for(int j=0;j<=c3+c4;j++)
			upd(sum[i][j],sum[i-1][j]);
	for(int i=0;i<=c1;i++)
		for(int j=0;j<=c2;j++)
		{
			int l1=min(r3-c1-c2+i+j,c3+c4),l2=min(min(r1-c2-c3-i+j,r2-c1-c3+i-j),c4);
			if(l1>=0 && l2>=0) upd(ans,(ll)Binom(c1,i)*Binom(c2,j)%mod*sum[l1][l2+c3]);
		}
	cout<<ans<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3348kb

input:

3
1 000
1 100
0 111

output:

7

result:

ok answer is '7'

Test #2:

score: 0
Accepted
time: 3ms
memory: 3404kb

input:

5
2 10110
0 11010
1 00000

output:

19

result:

ok answer is '19'

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 3648kb

input:

3
2 011
0 100
3 010

output:

10

result:

wrong answer expected '8', found '10'