QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563091#6653. 阴阳阵法ElegiaAC ✓67ms33684kbC++232.0kb2024-09-14 02:32:312024-09-14 02:32:31

Judging History

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

  • [2024-09-14 02:32:31]
  • 评测
  • 测评结果:AC
  • 用时:67ms
  • 内存:33684kb
  • [2024-09-14 02:32:31]
  • 提交

answer

#include <bits/stdc++.h>

using ull = unsigned long long;

int Mod;

int norm(int x) { return x >= Mod ? x - Mod : x; }
int reduce(int x) { return x < 0 ? x + Mod : x; }
int neg(int x) { return x ? Mod - x : 0; }
void add(int& x, int y) { if ((x += y - Mod) < 0) x += Mod; }
void sub(int& x, int y) { if ((x -= y) < 0) x += Mod; }
void fam(int& x, int y, int z) { x = (x + y * (ull)z) % Mod; }

const int _ = 2005;

int C[_][_], fac[_];
int f[_][_];
int pw1[_], pw2[_];

void pre(int n) {
	C[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= i; ++j)
			C[i][j] = norm(C[i - 1][j - 1] + C[i - 1][j]);
	}
	fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * (ull)i % Mod;
}

int main() {
	int n, m; std::cin >> n >> m >> Mod;
	
	pre(std::max(n, m));
	pw1[0] = 1; for (int i = 1; i <= n; ++i) pw1[i] = pw1[i - 1] * (ull)(n + m) % Mod;
	pw2[0] = 1; for (int i = 1; i <= m; ++i) pw2[i] = pw2[i - 1] * (ull)n % Mod;
	for (int i = 0; i <= n; ++i) pw1[i] = pw1[i] * (ull)C[n][i] % Mod;
	for (int i = 0; i <= m; ++i) pw2[i] = pw2[i] * (ull)C[m][i] % Mod * fac[m - i] % Mod;

	f[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= std::min(m, i); ++j) {
			if (j) f[i][j] = neg(f[i - 1][j - 1]);

			int val = (i - 1ULL) * (i - 2) % Mod;
			if (i >= 2) {
				            fam(f[i][j], val * 2, f[i - 2][j]);
				if (j >= 2) fam(f[i][j], val * 2, f[i - 2][j - 2]);
			}

			if (i >= 3) {
				if (j >= 1) fam(f[i][j], neg(val), f[i - 3][j - 1]);
				if (j >= 3) fam(f[i][j], val,      f[i - 3][j - 3]);
			}

			if (i >= 4) {
				val = (i - 1ULL) * (i - 2) % Mod * (i - 3) % Mod * (i - 4) % Mod;
				            fam(f[i][j], neg(val), f[i - 4][j]);
				if (j >= 2) fam(f[i][j], 2 * val,  f[i - 4][j - 2]);
				if (j >= 4) fam(f[i][j], neg(val), f[i - 4][j - 4]);
			}
		}
	}

	int ans = 0;
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= std::min(m, i); ++j)
			ans = (ans + pw1[n - i] * (ull)pw2[m - j] % Mod * f[i][j]) % Mod;
	std::cout << ans << '\n';

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 65ms
memory: 33684kb

input:

2000 1969 999999999

output:

770055336

result:

ok 1 number(s): "770055336"

Test #2:

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

input:

1888 1 8000000

output:

1719872

result:

ok 1 number(s): "1719872"

Test #3:

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

input:

1 2000 79993339

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 61ms
memory: 33152kb

input:

1999 1999 2000

output:

1696

result:

ok 1 number(s): "1696"

Test #5:

score: 0
Accepted
time: 41ms
memory: 30160kb

input:

1518 1838 998244853

output:

835766872

result:

ok 1 number(s): "835766872"

Test #6:

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

input:

16 1666 17795

output:

15253

result:

ok 1 number(s): "15253"

Test #7:

score: 0
Accepted
time: 67ms
memory: 33156kb

input:

2000 2000 1

output:

0

result:

ok 1 number(s): "0"

Test #8:

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

input:

19 69 4

output:

0

result:

ok 1 number(s): "0"

Test #9:

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

input:

62 62 63

output:

7

result:

ok 1 number(s): "7"

Test #10:

score: 0
Accepted
time: 44ms
memory: 33428kb

input:

1809 1998 536870912

output:

159234561

result:

ok 1 number(s): "159234561"