QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#572487#8942. Sugar Sweet 3yyyyxhAC ✓293ms8596kbC++142.6kb2024-09-18 14:54:212024-09-18 14:54:21

Judging History

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

  • [2024-09-18 14:54:21]
  • 评测
  • 测评结果:AC
  • 用时:293ms
  • 内存:8596kb
  • [2024-09-18 14:54:21]
  • 提交

answer

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1003,M=503,P=1000000007;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
int qp(int a,int b=P-2){
	int res=1;
	while(b){
		if(b&1) res=(ll)res*a%P;
		a=(ll)a*a%P;b>>=1;
	}
	return res;
}
int A,B,C,n,ex;
int fac[N],fiv[N];
int cb[N][N],pw[M][M];
int f[M],dp[M][M],arr[M][M];
int res[M];__int128 seq[M];
int getc(int u,int v){
	if(v>u||v<0) return 0;
	return cb[u][v];
}
int calc(int x,int y,int z){
	if(x>A||y>B||z>C) return 0;
	// A -> B i
	// A -> C x-i
	// B -> C C-z-x+i
	// B -> A y-C+z+x-i
	// C -> B B-y-i
	// C -> A z-B+y+i
	__int128 coe=0;
	for(int i=0;i<=B-y&&i<=x;++i) coe+=(__int128)getc(x,i)*getc(y,C-z-x+i)*getc(z,B-y-i);
	return coe%P;
}
int poly[N],sz;
int dpoly[N];
void prod(int v){
	for(int i=++sz;i;--i) poly[i]=(poly[i-1]+(ll)poly[i]*(P-v))%P;
}
void iprod(int v){
	if(v){
		int iv=qp(P-v);
		for(int i=0;i<sz;++i) dpoly[i]=(ll)(poly[i]-dpoly[i-1]+P)*iv%P;
	}
	else{
		for(int i=0;i<sz;++i) dpoly[i]=poly[i+1];
	}
}
int main(){
	A=read(),B=read(),C=read();n=A+B+C;ex=read();
	if(n&1){puts("0");return 0;}
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=(ll)fac[i-1]*i%P;
	fiv[n]=qp(fac[n]);
	for(int i=n;i;--i) fiv[i-1]=(ll)fiv[i]*i%P;
	for(int i=0;i<=n;++i)
		for(int j=0;j<=i;++j) cb[i][j]=(ll)fac[i]*fiv[j]%P*fiv[i-j]%P;
	n>>=1;
	for(int i=1;i<=n;++i){
		f[i]=getc(2*i-2,i-1)-getc(2*i-2,i);
		if(f[i]<0) f[i]+=P;
	}
	dp[0][0]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=i;++j){
			__int128 cur=0;
			for(int x=1;x<=i;++x) cur+=(ll)dp[i-x][j-1]*f[x];
			dp[i][j]=cur%P;
		}
	for(int x=1;x<=n;++x){
		pw[x][0]=1;
		for(int i=1;i<=n;++i) pw[x][i]=(ll)pw[x][i-1]*x%P;
	}
	for(int x=0;x<=n;++x) arr[0][x]=1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j) dp[i][j]=(ll)dp[i][j]*fiv[j]%P;
		for(int x=1;x<=n;++x){
			__int128 cur=0;
			for(int j=1;j<=i;++j) cur+=(ll)pw[x][j]*dp[i][j];
			arr[i][x]=cur%P;
		}
	}
	for(int a=0;a<=A;++a)
		for(int b=0;b<=B;++b){
			int c=n-a-b;
			int sum=calc(a,b,c);
			if(!sum) continue;
			for(int i=0;i<=n;++i) seq[i]+=(__int128)arr[a][i]*arr[b][i]*arr[c][i]%P*sum;
		}
	poly[sz=1]=1;
	for(int i=1;i<=n;++i) prod(i);
	for(int i=0;i<=n;++i){
		iprod(i);
		int val=seq[i]%P*fiv[i]%P*fiv[n-i]%P;
		if((n^i)&1) val=P-val;
		for(int x=0;x<=n;++x) res[x]=(res[x]+(ll)dpoly[x]*val)%P;
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans=(ans+(ll)qp(i,ex)*res[i]%P*fac[i])%P;
	printf("%d\n",ans);
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3768kb

input:

1 2 3 1

output:

110

result:

ok 1 number(s): "110"

Test #2:

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

input:

4 5 7 12

output:

881078346

result:

ok 1 number(s): "881078346"

Test #3:

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

input:

1 1 7 8

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

13 26 88 45

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 101ms
memory: 8088kb

input:

100 300 400 1515897

output:

279831696

result:

ok 1 number(s): "279831696"

Test #6:

score: 0
Accepted
time: 96ms
memory: 7128kb

input:

120 310 298 1155114

output:

903227392

result:

ok 1 number(s): "903227392"

Test #7:

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

input:

1 1 2 1

output:

18

result:

ok 1 number(s): "18"

Test #8:

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

input:

5 5 10 1919810

output:

696652039

result:

ok 1 number(s): "696652039"

Test #9:

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

input:

1 1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 46ms
memory: 7544kb

input:

1 1 798 15154848

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 42ms
memory: 7920kb

input:

1 399 400 1616897

output:

987648925

result:

ok 1 number(s): "987648925"

Test #12:

score: 0
Accepted
time: 60ms
memory: 7596kb

input:

400 398 2 45458123

output:

830387421

result:

ok 1 number(s): "830387421"

Test #13:

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

input:

89 75 18 66278

output:

940243796

result:

ok 1 number(s): "940243796"

Test #14:

score: 0
Accepted
time: 293ms
memory: 8588kb

input:

333 333 334 1

output:

60970749

result:

ok 1 number(s): "60970749"

Test #15:

score: 0
Accepted
time: 292ms
memory: 8592kb

input:

334 333 333 1000000000

output:

159064905

result:

ok 1 number(s): "159064905"

Test #16:

score: 0
Accepted
time: 96ms
memory: 8524kb

input:

1 499 500 1515987

output:

880517266

result:

ok 1 number(s): "880517266"

Test #17:

score: 0
Accepted
time: 125ms
memory: 8592kb

input:

500 498 2 1514789

output:

93909141

result:

ok 1 number(s): "93909141"

Test #18:

score: 0
Accepted
time: 237ms
memory: 8532kb

input:

250 250 500 19198877

output:

172243832

result:

ok 1 number(s): "172243832"

Test #19:

score: 0
Accepted
time: 284ms
memory: 8596kb

input:

300 300 400 75787941

output:

778545661

result:

ok 1 number(s): "778545661"

Test #20:

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

input:

7 16 11 1568

output:

725510153

result:

ok 1 number(s): "725510153"

Extra Test:

score: 0
Extra Test Passed