QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#541572#8942. Sugar Sweet 3ucup-team3510#WA 367ms5468kbC++202.4kb2024-08-31 20:03:272024-08-31 20:03:27

Judging History

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

  • [2024-08-31 20:03:27]
  • 评测
  • 测评结果:WA
  • 用时:367ms
  • 内存:5468kb
  • [2024-08-31 20:03:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 1e9 + 7, N = 505;
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(500);
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 2 3 1

output:

110

result:

ok 1 number(s): "110"

Test #2:

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

input:

4 5 7 12

output:

881078346

result:

ok 1 number(s): "881078346"

Test #3:

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

input:

1 1 7 8

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

13 26 88 45

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Wrong Answer
time: 367ms
memory: 5468kb

input:

100 300 400 1515897

output:

355065582

result:

wrong answer 1st numbers differ - expected: '279831696', found: '355065582'