QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#69115 | #1245. Three balls | eyiigjkn | WA | 3ms | 3648kb | C++14 | 2.1kb | 2022-12-23 21:06:32 | 2022-12-23 21:06:33 |
Judging History
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'