QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#718611 | #8942. Sugar Sweet 3 | zyxawa | TL | 1ms | 3964kb | C++14 | 1.5kb | 2024-11-06 20:57:57 | 2024-11-06 20:57:58 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int u,v,w,x,n;
ll pre[2001]={1},inv[2001]={1},f[501][501];
ll sum,ans[501],h[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;
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);
f[0][0]=1;
for(int i=1;i<=n/2;i++){
f[i][1]=T(i);
for(int j=1;j<i;j++) (f[i][1]+=mod-f[j][1]*T(i-j)%mod)%=mod;
}
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<=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 ab=0;ab<=u-i&&ab<=j;ab++){
int ac=u-i-ab,cb=j-ab,ca=w-l-cb,ba=i-ca,bc=l-ac;
(s+=C(i,ca)*C(j,ab)%mod*C(l,ac))%=mod;
}
memset(h,0,sizeof(h));
for(int a=0;a<=n/2;a++){
for(int b=0;a+b<=n/2;b++){
(h[a+b]+=f[i][a]*f[j][b]%mod*inv[a]%mod*inv[b])%=mod;
}
}
for(int ab=0;ab<=n/2;ab++){
for(int c=0;c+ab<=n/2;c++){
(ans[ab+c]+=h[ab]*f[l][c]%mod*inv[c]%mod*s)%=mod;
}
}
}
}
for(int i=0;i<=n/2;i++) (sum+=pre[i]*ans[i]%mod*qpow(i,x))%=mod;
printf("%lld",sum);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3940kb
input:
1 2 3 1
output:
110
result:
ok 1 number(s): "110"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
4 5 7 12
output:
881078346
result:
ok 1 number(s): "881078346"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
1 1 7 8
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
13 26 88 45
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: -100
Time Limit Exceeded
input:
100 300 400 1515897