QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#760725 | #8942. Sugar Sweet 3 | zyxawa | AC ✓ | 890ms | 7924kb | C++14 | 1.5kb | 2024-11-18 18:48:38 | 2024-11-18 18:48:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int u,v,w,x,n;
ll sum,pre[2001],inv[2001],f[501][501],g[501][501],val[501],ans[501],dp[501];
const int mod=1e9+7;
ll C(int n,int m){
return n<m||m<0?0:pre[n]*inv[m]%mod*inv[n-m]%mod;
}
ll T(int n){
return (C(n*2,n)-C(n*2,n-1)+mod)%mod;
}
ll qpow(ll a,ll b){
ll s=1;
for(;b;b>>=1,a=a*a%mod) if(b&1) s=s*a%mod;
return s;
}
int main(){
scanf("%d%d%d%d",&u,&v,&w,&x),n=u+v+w,pre[0]=inv[0]=f[0][0]=1;
if(n%2||max({u,v,w})>n/2) return printf("0"),0;
for(int i=1;i<=2000;i++) pre[i]=pre[i-1]*i%mod,inv[i]=qpow(pre[i],mod-2);
for(int i=1;i<=n/2;i++) f[i][1]=T(i-1);
for(int k=2;k<=n/2;k++) for(int i=1;i<=n/2;i++) for(int j=1;i+j<=n/2;j++) (f[i+j][k]+=f[i][k-1]*f[j][1])%=mod;
for(int i=0;i<=n/2;i++) for(int j=0;j<=n/2;j++) for(int k=i;k>=0;k--) g[i][j]=(g[i][j]*j+f[i][k]*inv[k])%mod;
for(int i=0;i<=u&&i<=n/2;i++){
for(int j=0;j<=v&&i+j<=n/2;j++){
ll l=n/2-i-j,s=0;
for(int k=0;k<=u-i&&k<=j;k++) (s+=C(i,w-l-j+k)*C(j,k)%mod*C(l,u-i-k))%=mod;
for(int k=0;k<=n/2;k++) (val[k]+=g[i][k]*g[j][k]%mod*g[l][k]%mod*s)%=mod;
}
}
for(int i=0;i<=n/2;i++){
memset(dp,0,sizeof(dp)),dp[0]=1;
for(int j=0;j<=n/2;j++){
if(i==j) continue;
ll x=qpow(i-j+mod,mod-2),y=mod-j*x%mod;
for(int l=n/2;l>=0;l--) dp[l]=(dp[l]*y+(l>0?dp[l-1]:0)*x)%mod;
}
for(int j=0;j<=n/2;j++) (ans[j]+=dp[j]*val[i])%=mod;
}
for(int i=0;i<=n/2;i++) (sum+=pre[i]*ans[i]%mod*qpow(i,x))%=mod;
printf("%lld",sum);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5928kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5840kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 354ms
memory: 7480kb
input:
100 300 400 1515897
output:
279831696
result:
ok 1 number(s): "279831696"
Test #6:
score: 0
Accepted
time: 288ms
memory: 7192kb
input:
120 310 298 1155114
output:
903227392
result:
ok 1 number(s): "903227392"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5992kb
input:
1 1 2 1
output:
18
result:
ok 1 number(s): "18"
Test #8:
score: 0
Accepted
time: 1ms
memory: 6008kb
input:
5 5 10 1919810
output:
696652039
result:
ok 1 number(s): "696652039"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
1 1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
1 1 798 15154848
output:
0
result:
ok 1 number(s): "0"
Test #11:
score: 0
Accepted
time: 301ms
memory: 7292kb
input:
1 399 400 1616897
output:
987648925
result:
ok 1 number(s): "987648925"
Test #12:
score: 0
Accepted
time: 461ms
memory: 7472kb
input:
400 398 2 45458123
output:
830387421
result:
ok 1 number(s): "830387421"
Test #13:
score: 0
Accepted
time: 7ms
memory: 6344kb
input:
89 75 18 66278
output:
940243796
result:
ok 1 number(s): "940243796"
Test #14:
score: 0
Accepted
time: 846ms
memory: 7876kb
input:
333 333 334 1
output:
60970749
result:
ok 1 number(s): "60970749"
Test #15:
score: 0
Accepted
time: 859ms
memory: 7820kb
input:
334 333 333 1000000000
output:
159064905
result:
ok 1 number(s): "159064905"
Test #16:
score: 0
Accepted
time: 579ms
memory: 7680kb
input:
1 499 500 1515987
output:
880517266
result:
ok 1 number(s): "880517266"
Test #17:
score: 0
Accepted
time: 890ms
memory: 7924kb
input:
500 498 2 1514789
output:
93909141
result:
ok 1 number(s): "93909141"
Test #18:
score: 0
Accepted
time: 719ms
memory: 7724kb
input:
250 250 500 19198877
output:
172243832
result:
ok 1 number(s): "172243832"
Test #19:
score: 0
Accepted
time: 815ms
memory: 7668kb
input:
300 300 400 75787941
output:
778545661
result:
ok 1 number(s): "778545661"
Test #20:
score: 0
Accepted
time: 2ms
memory: 6072kb
input:
7 16 11 1568
output:
725510153
result:
ok 1 number(s): "725510153"
Extra Test:
score: 0
Extra Test Passed