QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#563091 | #6653. 阴阳阵法 | Elegia | AC ✓ | 67ms | 33684kb | C++23 | 2.0kb | 2024-09-14 02:32:31 | 2024-09-14 02:32:31 |
Judging History
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"