QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#722980#8942. Sugar Sweet 3yz_lyAC ✓1163ms12564kbC++143.8kb2024-11-07 20:47:292024-11-07 20:47:29

Judging History

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

  • [2024-11-07 20:47:29]
  • 评测
  • 测评结果:AC
  • 用时:1163ms
  • 内存:12564kb
  • [2024-11-07 20:47:29]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-f;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}
inline void write(ll k){
	if(k<0){
		putchar('-');
		k=-k;
	}
	if(k>9)
		write(k/10);
	putchar(k%10+'0');
}
/*
记n=U+V+W
当n为奇数的时候答案为0,因为一定消不完
长度为2*i的括号序列数量是卡特兰数第i项
预处理f[i][j]表示括号序列长度为2*i,有j个地方被消空的方案数,用卡特兰数计算就行,枚举最后一段和为0的,去掉边上一对,中间就是一个随意配对的卡特兰数
我们将牌堆中被消除的牌看成左括号,其它的看成右括号
枚举i,j表示小u,小v的牌作为左括号的次数,小w的次数就是n/2-i-j
第一部分的贡献就是左右括号如何配对
因为同一人的右括号不能与同一人的左括号配对,所以我们枚举一个k表示有多少个小u的右括号与小v的左括号配对,然后我们能够算出所有配对的情况
如小w的右括号与小v的左括号配对的个数就是j-k....,那么这一部分的贡献就用组合数很简单的算完了
第二部分就是有多少个配对完,并且如何排列
很暴力的枚举p1,p2,p3表示小u,小v,小w有多少个和为0的时刻,此时的方案数就是f[i][p1]*f[j][p2]*f[n/2-i-j][p3]*(p1+p2+p3)!/p1!/p2!/p3!
但是你发现这个东西相当于三个多项式f_i=sum(f[i][j]/j!*x^j),点值的横坐标取0~n/2就行,就直接对应点值相乘再插值回去就行了
两部分相乘即可
*/
const ll mod=1e9+7;
int n,U,V,W,x;
ll jc[2005],inv[2005],inv1[2005],dp[1005][1005],f[1005][1005],g[1005],ans[1005],res[1005],res1[1005],h[1005];
ll C(ll n,ll m){
	if(n<m||n<0||m<0)
		return 0;
	return jc[n]*inv[m]%mod*inv[n-m]%mod;
}
ll F(ll n){
	return C(2*n,n)*inv1[n+1]%mod;
}
ll power(ll a,ll b){
	ll sum=1,k=a;
	while(b){
		if(b&1ll)
			sum=sum*k%mod;
		k=k*k%mod;
		b>>=1ll;
	}
	return sum;
}
void solve(ll *y){
	for(int i=0;i<=n/2+1;i++){
		res[i]=0;
	}
	res[0]=1;
	for(int i=0;i<=n/2;i++){
		for(int j=n/2+1;j>=0;j--){
			res[j]=((j?res[j-1]:0)-i*res[j]%mod)%mod;
		}
	}
	for(int i=0;i<=n/2;i++){
		ll val=inv[i]*inv[n/2-i]%mod*((n/2-i)&1?-1:1)%mod;
		for(int j=0;j<=n/2+1;j++){
			res1[j]=-(res[j]-(j?res1[j-1]:0))*inv1[i]%mod;
		}
		for(int j=0;j<=n/2+1;j++){
			h[j]=(h[j]+y[i]*val%mod*res1[j]%mod)%mod;
		}
	}
	for(int i=0;i<=n/2;i++){
		y[i]=h[i];
	}
}
int main(){
	U=read();
	V=read();
	W=read();
	x=read();
	n=U+V+W;
	if(n&1){
		write(0);
		return 0;
	}
	jc[0]=inv[0]=inv[1]=jc[1]=inv1[1]=1;
	for(int i=2;i<=2e3;i++){
		jc[i]=jc[i-1]*i%mod;
		inv1[i]=inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
	for(int i=2;i<=2e3;i++){
		inv[i]=inv[i]*inv[i-1]%mod;
	}
	dp[0][0]=1;
	for(int i=1;i<=n/2;i++){
		for(int j=1;j<=i;j++){
			for(int k=0;k<i;k++){
				dp[i][j]=(dp[i][j]+dp[k][j-1]*F(i-k-1)%mod)%mod;
			}
		}
		for(int j=0;j<=n/2;j++){
			for(int k=i;k>=0;k--){
				f[i][j]=(f[i][j]*j%mod+dp[i][k]*inv[k]%mod)%mod;
			}
		}
	}
	for(int j=0;j<=n/2;j++){
		f[0][j]=(f[0][j]*j%mod+dp[0][0]*inv[0]%mod)%mod;
	}
	for(int i=0;i<=U;i++){
		for(int j=0;j<=V&&j+i<=n/2;j++){
			int p=n/2-i-j;
			ll sum=0;
			for(int k=max(j-(W-p),0);k<=U-i&&k<=j;k++){
				sum=(sum+C(j,k)*C(i,W-p-(j-k))%mod*C(p,U-i-k)%mod)%mod;
			}
			for(int k=0;k<=n/2;k++){
				ans[k]=(ans[k]+f[i][k]*f[j][k]%mod*f[n/2-i-j][k]%mod*sum%mod)%mod;
			}/*本来是要对k=0~n/2都做一次插值的,但是f(a)+f(b)=f(a+b),所以对总和做一次就行了,点值可以直接求*/
		}
	}
	solve(ans);
	ll ans1=0;
	for(int k=0;k<=n/2;k++){
		ans1=(ans1+ans[k]*power(k,x)%mod*jc[k]%mod)%mod;
	}
	write((ans1+mod)%mod);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5748kb

input:

1 2 3 1

output:

110

result:

ok 1 number(s): "110"

Test #2:

score: 0
Accepted
time: 1ms
memory: 5756kb

input:

4 5 7 12

output:

881078346

result:

ok 1 number(s): "881078346"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

1 1 7 8

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

13 26 88 45

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 492ms
memory: 9716kb

input:

100 300 400 1515897

output:

279831696

result:

ok 1 number(s): "279831696"

Test #6:

score: 0
Accepted
time: 396ms
memory: 9244kb

input:

120 310 298 1155114

output:

903227392

result:

ok 1 number(s): "903227392"

Test #7:

score: 0
Accepted
time: 1ms
memory: 5732kb

input:

1 1 2 1

output:

18

result:

ok 1 number(s): "18"

Test #8:

score: 0
Accepted
time: 1ms
memory: 5772kb

input:

5 5 10 1919810

output:

696652039

result:

ok 1 number(s): "696652039"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

1 1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 416ms
memory: 9616kb

input:

1 1 798 15154848

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 415ms
memory: 10584kb

input:

1 399 400 1616897

output:

987648925

result:

ok 1 number(s): "987648925"

Test #12:

score: 0
Accepted
time: 597ms
memory: 10288kb

input:

400 398 2 45458123

output:

830387421

result:

ok 1 number(s): "830387421"

Test #13:

score: 0
Accepted
time: 5ms
memory: 6152kb

input:

89 75 18 66278

output:

940243796

result:

ok 1 number(s): "940243796"

Test #14:

score: 0
Accepted
time: 1157ms
memory: 11748kb

input:

333 333 334 1

output:

60970749

result:

ok 1 number(s): "60970749"

Test #15:

score: 0
Accepted
time: 1163ms
memory: 12564kb

input:

334 333 333 1000000000

output:

159064905

result:

ok 1 number(s): "159064905"

Test #16:

score: 0
Accepted
time: 817ms
memory: 12240kb

input:

1 499 500 1515987

output:

880517266

result:

ok 1 number(s): "880517266"

Test #17:

score: 0
Accepted
time: 1155ms
memory: 11972kb

input:

500 498 2 1514789

output:

93909141

result:

ok 1 number(s): "93909141"

Test #18:

score: 0
Accepted
time: 1034ms
memory: 12508kb

input:

250 250 500 19198877

output:

172243832

result:

ok 1 number(s): "172243832"

Test #19:

score: 0
Accepted
time: 1119ms
memory: 11916kb

input:

300 300 400 75787941

output:

778545661

result:

ok 1 number(s): "778545661"

Test #20:

score: 0
Accepted
time: 1ms
memory: 5880kb

input:

7 16 11 1568

output:

725510153

result:

ok 1 number(s): "725510153"

Extra Test:

score: 0
Extra Test Passed