QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#275185#6653. 阴阳阵法alpha1022AC ✓64ms35152kbC++142.1kb2023-12-04 14:41:072023-12-04 14:41:07

Judging History

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

  • [2023-12-04 14:41:07]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:35152kb
  • [2023-12-04 14:41:07]
  • 提交

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;
int neg(int x) { return x ? mod - x : x; }
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 - R((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 - R((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);
}

詳細信息

Test #1:

score: 100
Accepted
time: 51ms
memory: 34976kb

input:

2000 1969 999999999

output:

770055336

result:

ok 1 number(s): "770055336"

Test #2:

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

input:

1888 1 8000000

output:

1719872

result:

ok 1 number(s): "1719872"

Test #3:

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

input:

1 2000 79993339

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 63ms
memory: 35152kb

input:

1999 1999 2000

output:

1696

result:

ok 1 number(s): "1696"

Test #5:

score: 0
Accepted
time: 54ms
memory: 29884kb

input:

1518 1838 998244853

output:

835766872

result:

ok 1 number(s): "835766872"

Test #6:

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

input:

16 1666 17795

output:

15253

result:

ok 1 number(s): "15253"

Test #7:

score: 0
Accepted
time: 59ms
memory: 34548kb

input:

2000 2000 1

output:

0

result:

ok 1 number(s): "0"

Test #8:

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

input:

19 69 4

output:

0

result:

ok 1 number(s): "0"

Test #9:

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

input:

62 62 63

output:

7

result:

ok 1 number(s): "7"

Test #10:

score: 0
Accepted
time: 64ms
memory: 33520kb

input:

1809 1998 536870912

output:

159234561

result:

ok 1 number(s): "159234561"