QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#515406#7759. Permutation Counting 2JWRuixi100 ✓1053ms5772kbC++202.6kb2024-08-11 17:36:462024-08-11 17:36:47

Judging History

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

  • [2024-08-11 17:36:47]
  • 评测
  • 测评结果:100
  • 用时:1053ms
  • 内存:5772kb
  • [2024-08-11 17:36:46]
  • 提交

answer

#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) static_cast<int>((v).size())
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;

using vi = vector<int>;
#endif

constexpr int N = 507;
int n, P;

using ui = unsigned;
using ull = unsigned long long;
using u128 = __uint128_t;

struct Barret {
  ui m;
  ull B;

  explicit Barret (ui p = 2) : 
    m(p), B(ull(-1) / p + 1) {}

  ui operator () (ull x) const {
    ull y = (u128(B) * x) >> 64;
    ull z = y * m;
    return x - z + (x < z ? m : 0);
  }
} mod;

IL void qm (int &x) {
  x += x >> 31 & P;
}

IL constexpr int qpow (int b, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, b = mod((LL)b * b)) if (k & 1) r = mod((LL)r * b);
  return r;
}

int fc[N], ifc[N], C[N][N];

void init (int Z) {
  fc[0] = 1;
  L (i, 1, Z) {
    fc[i] = mod((LL)fc[i - 1] * i);
  }
  ifc[Z] = qpow(fc[Z]);
  R (i, Z - 1, 0) {
    ifc[i] = mod((LL)ifc[i + 1] * (i + 1));
  }
  L (i, 0, Z) {
    C[i][0] = 1;
    L (j, 1, i) {
      qm(C[i][j] = C[i - 1][j] + C[i - 1][j - 1] - P);
    }
  }
}

int f[N][N];

IL int com (int x) {
  int ret = ifc[n];
  L (i, 1, n) {
    ret = mod((LL)ret * (x + n - i));
  }
  return ret;
}

IL int sgn (int x) {
  return x & 1 ? -1 : 1;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> P;
  mod = Barret(P);
  init(n);
  L (i, 0, n) {
    L (j, 0, n) {
      f[i][j] = com(mod((LL)i * j));
    }
  }
  L (i, 0, n) {
    R (j, n, 0) {
      __int128 cur = 0;
      L (k, 0, j) {
        cur += (LL)sgn(k) * f[i][j - k] * C[j][k];
      }
      f[i][j] = (cur % P + P) % P;
    }
  }
  L (j, 0, n) {
    R (i, n, 0) {
      __int128 cur = 0;
      L (k, 0, i) {
        cur += (LL)sgn(k) * f[i - k][j] * C[i][k];
      }
      f[i][j] = (cur % P + P) % P;
    }
  }
  L (i, 0, n) {
    R (j, n, 0) {
      __int128 cur = 0;
      L (k, 0, j) {
        cur += (LL)sgn(j - k) * C[n - k][n - j] * f[i][k];
      }
      f[i][j] = (cur % P + P) % P;
    }
  }
  L (j, 0, n) {
    R (i, n, 0) {
      __int128 cur = 0;
      L (k, 0, i) {
        cur += (LL)sgn(i - k) * C[n - k][n - i] * f[k][j];
      }
      f[i][j] = (cur % P + P) % P;
    }
  }
  L (i, 0, n - 1) {
    L (j, 0, n - 1) {
      cout << f[n - i][n - j] << ' ';
    }
    cout << '\n';
  }
}
// I love WHQ!

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 3576kb

input:

7 1001458121

output:

1 0 0 0 0 0 0 
0 56 56 8 0 0 0 
0 56 659 440 36 0 0 
0 8 440 1520 440 8 0 
0 0 36 440 659 56 0 
0 0 0 8 56 56 0 
0 0 0 0 0 0 1 

result:

ok 49 tokens

Test #2:

score: 10
Accepted
time: 0ms
memory: 3628kb

input:

8 1008735209

output:

1 0 0 0 0 0 0 0 
0 84 126 36 1 0 0 0 
0 126 1773 1980 405 9 0 0 
0 36 1980 8436 4761 405 1 0 
0 1 405 4761 8436 1980 36 0 
0 0 9 405 1980 1773 126 0 
0 0 0 1 36 126 84 0 
0 0 0 0 0 0 0 1 

result:

ok 64 tokens

Subtask #2:

score: 15
Accepted

Test #3:

score: 15
Accepted
time: 1ms
memory: 3652kb

input:

14 1000253273

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 455 3003 6435 5005 1365 105 1 0 0 0 0 0 0 
0 3003 112905 730665 1629435 1456560 529956 71940 2835 15 0 0 0 0 
0 6435 730665 10865585 46433475 75169560 50184540 13633740 1349931 36735 120 0 0 0 
0 5005 1629435 46433475 336576825 860578230 885230850 375891370 62035485 33...

result:

ok 196 tokens

Test #4:

score: 15
Accepted
time: 0ms
memory: 3604kb

input:

15 1009800301

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 560 4368 11440 11440 4368 560 16 0 0 0 0 0 0 0 
0 4368 188682 1482416 4160120 4899264 2511376 536384 41328 800 1 0 0 0 0 
0 11440 1482416 26232784 139089120 291102560 265085216 106311200 17712368 1048560 15232 16 0 0 0 
0 11440 4160120 139089120 216926039 947184153 3...

result:

ok 225 tokens

Test #5:

score: 15
Accepted
time: 0ms
memory: 3600kb

input:

16 1006729121

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 680 6188 19448 24310 12376 2380 136 1 0 0 0 0 0 0 0 
0 6188 305150 2867696 9916066 14924539 10288876 3196000 410329 17748 153 0 0 0 0 0 
0 19448 2867696 59852036 387206263 15304436 216863763 683915984 173666645 18275272 650641 4828 1 0 0 0 
0 24310 9916066 38720626...

result:

ok 256 tokens

Subtask #3:

score: 25
Accepted

Test #6:

score: 25
Accepted
time: 2ms
memory: 3680kb

input:

36 1003299797

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 7770 435897 10295472 124403620 854992152 552567909 334501587 855871755 616535351 836177106 87288018 849183199 348330136 38608020 2324784 66045 666 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 435897 133844910 939232742 752696285 94...

result:

ok 1296 tokens

Test #7:

score: 25
Accepted
time: 1ms
memory: 3752kb

input:

37 1009736899

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 8436 501942 12620256 163011640 193585389 366265801 325233075 508510208 4472335 508510208 325233075 366265801 193585389 163011640 12620256 501942 8436 38 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 501942 164674938 380061172 7953...

result:

ok 1369 tokens

Test #8:

score: 25
Accepted
time: 1ms
memory: 3760kb

input:

38 1002064493

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 9139 575757 15380937 211915132 673991551 105909500 89228335 917893160 782878886 231145424 634874749 53537001 904603957 635745396 61523748 3262623 82251 741 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 575757 201514950 2661126...

result:

ok 1444 tokens

Test #9:

score: 25
Accepted
time: 1ms
memory: 3984kb

input:

39 1000696681

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 9880 658008 18643560 273438880 310408078 24862708 197477816 671070872 191143189 191143189 671070872 197477816 24862708 310408078 273438880 18643560 658008 9880 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 658008 24533645...

result:

ok 1521 tokens

Test #10:

score: 25
Accepted
time: 1ms
memory: 3684kb

input:

40 1002813283

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 10660 749398 22481940 350343565 151022119 572250549 255038067 159674717 979042431 374977376 547170717 790491840 141687815 878961939 118286125 95548245 4496388 101270 820 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 7493...

result:

ok 1600 tokens

Subtask #4:

score: 25
Accepted

Test #11:

score: 25
Accepted
time: 5ms
memory: 3924kb

input:

96 1005401729

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 147440 64446024 781420036 468430311 27733626 62151757 454795566 711626792 885805006 401110492 711423106 3...

result:

ok 9216 tokens

Test #12:

score: 25
Accepted
time: 8ms
memory: 4012kb

input:

97 1003022927

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 152096 67910864 795115101 924546504 230011659 577127906 564913191 11843263 171607987 697964156 4314087 ...

result:

ok 9409 tokens

Test #13:

score: 25
Accepted
time: 9ms
memory: 4208kb

input:

98 1000259233

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 156849 71523144 883402282 582472554 858367843 730708960 476781508 806308877 286962083 221796390 32768...

result:

ok 9604 tokens

Test #14:

score: 25
Accepted
time: 9ms
memory: 3992kb

input:

99 1000444889

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 161700 75287520 442576 386074411 823487426 504618380 971268883 734797176 388493421 848753352 857480...

result:

ok 9801 tokens

Test #15:

score: 25
Accepted
time: 9ms
memory: 4008kb

input:

100 1008746839

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 166650 79208745 50916937 213745970 953400361 882774939 595265332 362179793 339853992 820776686 20...

result:

ok 10000 tokens

Subtask #5:

score: 25
Accepted

Test #16:

score: 25
Accepted
time: 1024ms
memory: 5496kb

input:

496 1005266363

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 246016 tokens

Test #17:

score: 25
Accepted
time: 1029ms
memory: 5504kb

input:

497 1000331767

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 247009 tokens

Test #18:

score: 25
Accepted
time: 1029ms
memory: 5604kb

input:

498 1000148759

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 248004 tokens

Test #19:

score: 25
Accepted
time: 1038ms
memory: 5600kb

input:

499 1000176851

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 249001 tokens

Test #20:

score: 25
Accepted
time: 1053ms
memory: 5772kb

input:

500 1002873259

output:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

result:

ok 250000 tokens