QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#760725#8942. Sugar Sweet 3zyxawaAC ✓890ms7924kbC++141.5kb2024-11-18 18:48:382024-11-18 18:48:39

Judging History

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

  • [2024-11-18 18:48:39]
  • 评测
  • 测评结果:AC
  • 用时:890ms
  • 内存:7924kb
  • [2024-11-18 18:48:38]
  • 提交

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