QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#542216#8942. Sugar Sweet 3ucup-team4504#AC ✓2195ms10076kbC++142.7kb2024-08-31 23:28:392024-08-31 23:28:39

Judging History

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

  • [2024-08-31 23:28:39]
  • 评测
  • 测评结果:AC
  • 用时:2195ms
  • 内存:10076kb
  • [2024-08-31 23:28:39]
  • 提交

answer

//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define MOD 1000000007
using namespace __gnu_pbds;
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int n,A,B,C,x,pw[2010],rev[2010],pwm[1010],val[1010][1010],f[1010],dp[1010][1010];

inline void add1(int &x,int y)
{
	x+=y;
	if(x>=MOD) x-=MOD;
}

inline void add2(int &x,int y)
{
	x+=y;
	if(x<0) x+=MOD;
}

inline int my_pow(int x,int y)
{
	if(y==0) return 1;
	if(y==1) return x;
	int res=my_pow(x,y/2);
	if(y%2==0) return 1ll*res*res%MOD;
	else return 1ll*res*res%MOD*x%MOD;
}

inline int calc(int x,int y)
{
	if(x<0||y<0||x<y) return 0;
	return 1ll*pw[x]*rev[y]%MOD*rev[x-y]%MOD; 
}

signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>A>>B>>C>>x;
	if(A>B) swap(A,B);
	if(A>C) swap(A,C);
	if(B>C) swap(B,C);
	n=A+B+C;
	if(n%2!=0){
		cout<<0<<'\n';
		return 0;
	}
	int M=(A+B+C)/2;
	pw[0]=1;
	for(int i=1;i<=2*n;i++) pw[i]=1ll*pw[i-1]*i%MOD;
	rev[2*n]=my_pow(pw[2*n],MOD-2);
	for(int i=2*n-1;i>=0;i--) rev[i]=1ll*rev[i+1]*(i+1)%MOD;
	for(int i=0;i<=n;i++){
		pwm[i]=my_pow(i,x);
	}
	for(int i=0;i<=A;i++){
		for(int j=0;j<=B;j++) if(i+j<=M){
			val[i][j]=0;
			for(int a=0;a<=j;a++){
				add1(val[i][j],1ll*calc(i,C-M+i+a)*calc(j,a)%MOD*calc(M-i-j,A-i-a)%MOD);
			}
		}
	}
	for(int i=0;i<n;i++) f[i+1]=1ll*calc(2*i,i)*my_pow(i+1,MOD-2)%MOD;
	dp[0][0]=1;
	for(int i=1;i<=M;i++){
		dp[i][1]=f[i];
		for(int j=2;j<=i;j++){
			for(int k=1;k<i;k++) add1(dp[i][j],1ll*f[k]*dp[i-k][j-1]%MOD);
		}
	}
	for(int i=1;i<=M;i++){
		for(int j=1;j<=i;j++){
			dp[i][j]=1ll*dp[i][j]*rev[j]%MOD;
		}
	}
	int ans=0;
	for(int S=0;S<=M;S++){
		int Z=M-S;
		for(int O=0;O<=S;O++){
			int tot=0;
			for(int X=max(S-B,0);X<=min(A,S);X++) if(val[X][S-X]){
				int Y=S-X;
				__int128 res=0;
				for(int i=max(O-Y,0);i<=min(X,O);i++){
					int j=O-i;
					res+=1ll*dp[X][i]*dp[Y][j];
				}
				add1(tot,1ll*val[X][Y]*(res%MOD)%MOD);
			}
			for(int k=0;k<=Z;k++){
				int cur=1ll*pwm[O+k]*pw[O+k]%MOD;
				cur=1ll*cur*dp[Z][k]%MOD;
				add1(ans,1ll*cur*tot%MOD);
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 2 3 1

output:

110

result:

ok 1 number(s): "110"

Test #2:

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

input:

4 5 7 12

output:

881078346

result:

ok 1 number(s): "881078346"

Test #3:

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

input:

1 1 7 8

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

13 26 88 45

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 365ms
memory: 8708kb

input:

100 300 400 1515897

output:

279831696

result:

ok 1 number(s): "279831696"

Test #6:

score: 0
Accepted
time: 390ms
memory: 9936kb

input:

120 310 298 1155114

output:

903227392

result:

ok 1 number(s): "903227392"

Test #7:

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

input:

1 1 2 1

output:

18

result:

ok 1 number(s): "18"

Test #8:

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

input:

5 5 10 1919810

output:

696652039

result:

ok 1 number(s): "696652039"

Test #9:

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

input:

1 1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 103ms
memory: 8668kb

input:

1 1 798 15154848

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 107ms
memory: 7468kb

input:

1 399 400 1616897

output:

987648925

result:

ok 1 number(s): "987648925"

Test #12:

score: 0
Accepted
time: 102ms
memory: 7244kb

input:

400 398 2 45458123

output:

830387421

result:

ok 1 number(s): "830387421"

Test #13:

score: 0
Accepted
time: 3ms
memory: 5976kb

input:

89 75 18 66278

output:

940243796

result:

ok 1 number(s): "940243796"

Test #14:

score: 0
Accepted
time: 2195ms
memory: 8904kb

input:

333 333 334 1

output:

60970749

result:

ok 1 number(s): "60970749"

Test #15:

score: 0
Accepted
time: 2193ms
memory: 9700kb

input:

334 333 333 1000000000

output:

159064905

result:

ok 1 number(s): "159064905"

Test #16:

score: 0
Accepted
time: 195ms
memory: 7816kb

input:

1 499 500 1515987

output:

880517266

result:

ok 1 number(s): "880517266"

Test #17:

score: 0
Accepted
time: 210ms
memory: 8516kb

input:

500 498 2 1514789

output:

93909141

result:

ok 1 number(s): "93909141"

Test #18:

score: 0
Accepted
time: 1166ms
memory: 10076kb

input:

250 250 500 19198877

output:

172243832

result:

ok 1 number(s): "172243832"

Test #19:

score: 0
Accepted
time: 1831ms
memory: 10000kb

input:

300 300 400 75787941

output:

778545661

result:

ok 1 number(s): "778545661"

Test #20:

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

input:

7 16 11 1568

output:

725510153

result:

ok 1 number(s): "725510153"

Extra Test:

score: 0
Extra Test Passed