QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#541585#8942. Sugar Sweet 3ucup-team3510#AC ✓839ms9848kbC++202.4kb2024-08-31 20:06:042024-08-31 20:06:04

Judging History

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

  • [2024-08-31 20:06:04]
  • 评测
  • 测评结果:AC
  • 用时:839ms
  • 内存:9848kb
  • [2024-08-31 20:06:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 1e9 + 7, N = 1005;
int fac[N], inv[N], iv[N], F[N][N], G[N][N], H[N], X[N], Y[N];
int qpow(int x, int y)
{
	int ans = 1;
	while(y)
	{
		if(y & 1)
			ans = (ll)ans * x % mod;
		x = (ll)x * x % mod;
		y >>= 1;
	}
	return ans;
}
void prep(int n)
{
	int i;
	fac[0] = 1;
	for(i = 1; i <= n; i++)
		fac[i] = (ll)fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2);
	for(i = n; i >= 1; i--)
		inv[i - 1] = (ll)inv[i] * i % mod;
	for(i = 1; i <= n; i++)
		iv[i] = (ll)inv[i] * fac[i - 1] % mod;
}
int Ch(int x, int y)
{
	return (x < y || y < 0) ? 0 : ((ll)fac[x] * inv[y] % mod * inv[x - y] % mod);
}

int main()
{
	int A, B, C, x, i, j, k, n, u, v, w, d, ans = 0;
	prep(1000);
	scanf("%d%d%d%d", &A, &B, &C, &x);
	if((A + B + C) & 1)
	{
		printf("0\n");
		return 0;
	}
	n = (A + B + C) / 2;
	F[0][0] = 1;
	for(i = 1; i <= n; i++)
		F[1][i] = (ll)Ch(2 * i - 2, i - 1) * iv[i] % mod;
	for(i = 2; i <= n; i++)
		for(j = i - 1; j <= n; j++)
			for(k = 1; k <= n - j; k++)
				F[i][j + k] = (F[i][j + k] + (ll)F[i - 1][j] * F[1][k]) % mod;
	for(i = 0; i <= n; i++)
		for(j = 0; j <= n; j++)
			F[i][j] = (ll)F[i][j] * inv[i] % mod;
	for(i = 0; i <= n; i++)
		for(j = 0; j <= n; j++)
			for(k = n; k >= 0; k--)
				G[i][j] = ((ll)G[i][j] * j + F[k][i]) % mod;
	for(i = 0; i <= A; i++)
		for(j = 0; j <= B; j++)
		{
			k = n - i - j;
			if(k > C || k < 0)
				continue;
			d = 0;
			for(w = 0; w <= C - k; w++)
			{
				v = w - (i + j - B);
				u = v - (k + i - A);
				if(u > A - i || u < 0)
					continue;
				if(v > B - j || v < 0)
					continue;
				d = (d + (ll)Ch(i, w) * Ch(j, u) % mod * Ch(k, v)) % mod;
			}
			// printf("!!%d %d %d %d\n", i, j, k, d);
			for(w = 0; w <= n; w++)
				H[w] = (H[w] + (ll)G[i][w] * G[j][w] % mod * G[k][w] % mod * d) % mod;
		}
	for(i = 0; i <= n; i++)
	{
		H[i] = (ll)H[i] * inv[i] % mod * inv[n - i] % mod;
		if((i & 1) != (n & 1))
			H[i] = mod - H[i];
	}
	Y[0] = 1;
	for(i = 0; i <= n; i++)
		for(j = i + 1; j >= 0; j--)
		{
			X[j] = ((j ? X[j - 1] : 0) + (ll)(mod - i) * X[j] + (ll)H[i] * Y[j]) % mod;
			Y[j] = ((j ? Y[j - 1] : 0) + (ll)(mod - i) * Y[j]) % mod;
		}
	for(i = 0; i <= n; i++)
	{
		X[i] = (ll)X[i] * fac[i] % mod;
		// printf("??%d\n", X[i]);
		ans = (ans + (ll)X[i] * qpow(i, x)) % mod;
	}
	printf("%d\n", ans);
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 2 3 1

output:

110

result:

ok 1 number(s): "110"

Test #2:

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

input:

4 5 7 12

output:

881078346

result:

ok 1 number(s): "881078346"

Test #3:

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

input:

1 1 7 8

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

13 26 88 45

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 367ms
memory: 7772kb

input:

100 300 400 1515897

output:

279831696

result:

ok 1 number(s): "279831696"

Test #6:

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

input:

120 310 298 1155114

output:

903227392

result:

ok 1 number(s): "903227392"

Test #7:

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

input:

1 1 2 1

output:

18

result:

ok 1 number(s): "18"

Test #8:

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

input:

5 5 10 1919810

output:

696652039

result:

ok 1 number(s): "696652039"

Test #9:

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

input:

1 1 1 1

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 304ms
memory: 8752kb

input:

1 1 798 15154848

output:

0

result:

ok 1 number(s): "0"

Test #11:

score: 0
Accepted
time: 313ms
memory: 8428kb

input:

1 399 400 1616897

output:

987648925

result:

ok 1 number(s): "987648925"

Test #12:

score: 0
Accepted
time: 318ms
memory: 8048kb

input:

400 398 2 45458123

output:

830387421

result:

ok 1 number(s): "830387421"

Test #13:

score: 0
Accepted
time: 2ms
memory: 6656kb

input:

89 75 18 66278

output:

940243796

result:

ok 1 number(s): "940243796"

Test #14:

score: 0
Accepted
time: 839ms
memory: 9848kb

input:

333 333 334 1

output:

60970749

result:

ok 1 number(s): "60970749"

Test #15:

score: 0
Accepted
time: 830ms
memory: 9648kb

input:

334 333 333 1000000000

output:

159064905

result:

ok 1 number(s): "159064905"

Test #16:

score: 0
Accepted
time: 612ms
memory: 9016kb

input:

1 499 500 1515987

output:

880517266

result:

ok 1 number(s): "880517266"

Test #17:

score: 0
Accepted
time: 618ms
memory: 8976kb

input:

500 498 2 1514789

output:

93909141

result:

ok 1 number(s): "93909141"

Test #18:

score: 0
Accepted
time: 744ms
memory: 8776kb

input:

250 250 500 19198877

output:

172243832

result:

ok 1 number(s): "172243832"

Test #19:

score: 0
Accepted
time: 823ms
memory: 9772kb

input:

300 300 400 75787941

output:

778545661

result:

ok 1 number(s): "778545661"

Test #20:

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

input:

7 16 11 1568

output:

725510153

result:

ok 1 number(s): "725510153"

Extra Test:

score: 0
Extra Test Passed