QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#514199 | #7759. Permutation Counting 2 | JWRuixi | 100 ✓ | 2994ms | 5696kb | C++20 | 2.3kb | 2024-08-10 22:57:11 | 2024-08-10 22:57:11 |
Judging History
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;
IL constexpr int qpow (int b, int k = P - 2) {
int r = 1;
for (; k; k >>= 1, b = (LL)b * b % P) if (k & 1) r = (LL)r * b % P;
return r;
}
int fc[N], ifc[N];
void init (int Z) {
fc[0] = 1;
L (i, 1, Z) {
fc[i] = (LL)fc[i - 1] * i % P;
}
ifc[Z] = qpow(fc[Z]);
R (i, Z - 1, 0) {
ifc[i] = (LL)ifc[i + 1] * (i + 1) % P;
}
}
IL int C (int n, int m) {
return (LL)fc[n] * ifc[m] % P * ifc[n - m] % P;
}
int f[N][N], g[N][N];
IL int com (int x) {
int ret = ifc[n];
L (i, 1, n) {
ret = (LL)ret * (x + n - i) % P;
}
return ret;
}
IL int sgn (int x) {
return x & 1 ? -1 : 1;
}
void copy () {
L (i, 0, n) {
L (j, 0, n) {
f[i][j] = g[i][j];
}
}
}
int main () {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> P;
init(n);
L (i, 0, n) {
L (j, 0, n) {
f[i][j] = com((LL)i * j % P);
}
}
L (i, 0, n) {
L (j, 0, n) {
int cur = 0;
L (k, 0, j) {
cur = (cur + (LL)sgn(k) * f[i][j - k] * C(j, k)) % P;
}
g[i][j] = (cur % P + P) % P;
}
}
copy();
L (j, 0, n) {
L (i, 0, n) {
int cur = 0;
L (k, 0, i) {
cur = (cur + (LL)sgn(k) * f[i - k][j] * C(i, k)) % P;
}
g[i][j] = (cur % P + P) % P;
}
}
copy();
L (i, 0, n) {
L (j, 0, n) {
int cur = 0;
L (k, 0, j) {
cur = (cur + (LL)sgn(j - k) * C(n - k, n - j) * f[i][k]) % P;
}
g[i][j] = (cur % P + P) % P;
}
}
copy();
L (j, 0, n) {
L (i, 0, n) {
int cur = 0;
L (k, 0, i) {
cur = (cur + (LL)sgn(i - k) * C(n - k, n - i) * f[k][j]) % P;
}
g[i][j] = (cur % P + P) % P;
}
}
copy();
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: 0ms
memory: 3664kb
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: 3680kb
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: 0ms
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: 1ms
memory: 3728kb
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: 1ms
memory: 3732kb
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: 3784kb
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: 2ms
memory: 3796kb
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: 0ms
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: 2ms
memory: 3808kb
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: 0ms
memory: 3880kb
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: 19ms
memory: 4096kb
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: 23ms
memory: 4096kb
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: 20ms
memory: 4056kb
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: 24ms
memory: 3980kb
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: 25ms
memory: 4048kb
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: 2921ms
memory: 5556kb
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: 2947ms
memory: 5628kb
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: 2960ms
memory: 5696kb
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: 2983ms
memory: 5632kb
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: 2994ms
memory: 5580kb
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