QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#718611#8942. Sugar Sweet 3zyxawaTL 1ms3964kbC++141.5kb2024-11-06 20:57:572024-11-06 20:57:58

Judging History

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

  • [2024-11-06 20:57:58]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3964kb
  • [2024-11-06 20:57:57]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: