QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#275183 | #6653. 阴阳阵法 | alpha1022 | WA | 66ms | 35116kb | C++14 | 2.0kb | 2023-12-04 14:38:05 | 2023-12-04 14:38:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(-1ULL / b) {}
ull operator()(ull a) { ull r = a - (ull)((__uint128_t(m) * a) >> 64) * b; return r >= b ? r - b : r; }
} R(2);
int mod;
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; }
const int N = 2e3;
int n, m;
int fac[N + 5], binom[N + 5][N + 5];
int f[N + 5][N + 5];
int ans;
int main() {
scanf("%d%d%d", &n, &m, &mod), R = FastMod(mod);
fac[0] = 1;
for (int i = 1; i <= max(n, m); ++i) fac[i] = R((ull)fac[i - 1] * i);
for (int i = 0; i <= max(n, m); ++i) {
binom[i][0] = 1;
for (int j = 1; j <= i; ++j) add(binom[i][j] = binom[i - 1][j], binom[i - 1][j - 1]);
}
f[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) sub(f[i][j], f[i - 1][j - 1]);
if (i == 1) continue;
int coef = 2 * (i - 1) * (i - 2);
for (int j = 0; j <= m; ++j) f[i][j] = R(f[i][j] + (ull)coef * f[i - 2][j]);
for (int j = 2; j <= m; ++j) f[i][j] = R(f[i][j] + (ull)coef * f[i - 2][j - 2]);
if (i == 2) continue;
coef = (mod - (i - 1) * (i - 2));
for (int j = 1; j <= m; ++j) f[i][j] = R(f[i][j] + (ull)coef * f[i - 3][j - 1]);
for (int j = 3; j <= m; ++j) f[i][j] = R(f[i][j] + (ull)(mod - coef) * f[i - 3][j - 3]);
if (i == 3) continue;
coef = R((ull)(mod - (i - 1) * (i - 2)) * (i - 3) * (i - 4));
for (int j = 0; j <= m; ++j) f[i][j] = R(f[i][j] + (ull)coef * f[i - 4][j]);
for (int j = 2; j <= m; ++j) f[i][j] = R(f[i][j] + 2ull * (mod - coef) * f[i - 4][j - 2]);
for (int j = 4; j <= m; ++j) f[i][j] = R(f[i][j] + (ull)coef * f[i - 4][j - 4]);
}
for (int i = 0, pw0 = 1; i <= n; ++i, pw0 = R((ull)pw0 * (n + m)))
for (int j = 0, pw1 = pw0; j <= m; ++j, pw1 = R((ull)pw1 * n))
ans = R(ans + R(R(R((ull)pw1 * binom[m][j]) * fac[m - j]) * binom[n][i]) * f[n - i][m - j]);
printf("%d\n", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 66ms
memory: 35004kb
input:
2000 1969 999999999
output:
770055336
result:
ok 1 number(s): "770055336"
Test #2:
score: 0
Accepted
time: 0ms
memory: 26536kb
input:
1888 1 8000000
output:
1719872
result:
ok 1 number(s): "1719872"
Test #3:
score: 0
Accepted
time: 6ms
memory: 21172kb
input:
1 2000 79993339
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 61ms
memory: 35116kb
input:
1999 1999 2000
output:
1696
result:
ok 1 number(s): "1696"
Test #5:
score: 0
Accepted
time: 49ms
memory: 30224kb
input:
1518 1838 998244853
output:
835766872
result:
ok 1 number(s): "835766872"
Test #6:
score: 0
Accepted
time: 1ms
memory: 16996kb
input:
16 1666 17795
output:
15253
result:
ok 1 number(s): "15253"
Test #7:
score: 0
Accepted
time: 59ms
memory: 35008kb
input:
2000 2000 1
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
19 69 4
output:
0
result:
ok 1 number(s): "0"
Test #9:
score: -100
Wrong Answer
time: 1ms
memory: 5956kb
input:
62 62 63
output:
25
result:
wrong answer 1st numbers differ - expected: '7', found: '25'