QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#422562 | #7759. Permutation Counting 2 | fireince | 0 | 1342ms | 14476kb | C++14 | 2.0kb | 2024-05-27 16:16:33 | 2024-05-27 16:16:33 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<array>
#define endl '\n'
using namespace std;
using ll = long long;
using pi2 = array<int,2>;
using pi3 = array<int,3>;
int n,P;
const int N=505,FN=N*N;
ll fpow(ll a,ll b){
return b==0?1:(b&1?a*fpow(a*a%P,b/2)%P:fpow(a*a%P,b/2));
}
ll fact[FN],inv_fact[FN];
void init_fact(int n){
fact[0] = inv_fact[0] = 1;
for (int i = 1; i <= n; i++)
fact[i] = 1ll*fact[i - 1] * i % P;
inv_fact[n] = fpow(fact[n], P - 2);
for (int i = n - 1; i >= 1; i--)
inv_fact[i] = 1ll*inv_fact[i + 1] * (i + 1) % P;
}
ll binom(ll n,ll k){
if(n<k)return 0;
return 1ll*fact[n]*inv_fact[k]%P*inv_fact[n-k]%P;
}
int f[N][N],g[N][N],h[N][N],a[N][N],b[N][N],C[N][N];
//
int T_(int a,int b){
return binom(n+a*b-1,a*b-1);
}
int T[N][N];
void mod(int& x){
if(x>=P)x-=P;
if(x<0)x+=P;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
n=500,P=998244353;
cin>>n>>P;
init_fact(n*n+n);
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++)T[i][j]=T_(i,j),C[i][j]=binom(i,j);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<=i;k++)
mod(f[i][j]+=T[i-k][j]*((k&1)?-1:1)*C[i][k]%P);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<=j;k++)
mod(g[i][j]+=f[i][j-k]*((k&1)?-1:1)*C[j][k]%P);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
h[n-i][n-j]=g[i][j];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=j;k<n;k++)
mod(a[i][j]+=h[i][k]*C[k][j]%P*(((j-k)%2)?-1:1));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
for(int k=i;k<n;k++)
mod(b[i][j]+=a[k][j]*C[k][i]%P*(((i-k)%2)?-1:1));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
cout<<b[i][j]<<" ";
cout<<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 0ms
memory: 3788kb
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: 0
Wrong Answer
time: 0ms
memory: 3812kb
input:
8 1008735209
output:
53679851 685967487 260026460 0 0 0 0 0 748708749 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:
wrong answer 1st words differ - expected: '1', found: '53679851'
Subtask #2:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 1ms
memory: 3840kb
input:
14 1000253273
output:
120988320 934119839 118465633 24928644 542196796 174774777 841828988 930812520 704676292 559931735 110544927 502186618 261050704 0 508354348 338574235 265765362 61349015 440478059 973310672 872612265 524540863 580832196 854411783 485228077 56084234 641036393 0 206927523 994241396 213533327 3632347...
result:
wrong answer 1st words differ - expected: '1', found: '120988320'
Subtask #3:
score: 0
Wrong Answer
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 4240kb
input:
36 1003299797
output:
584112747 537597731 713464957 35713637 792541171 569119090 443891147 562878778 638648380 85190216 701751758 409158720 432583429 675424390 184842791 938320197 394063083 357603416 946668487 657277620 25721390 393483981 436396302 603942728 394384421 502656404 23231078 194713389 881544520 135710639 6853...
result:
wrong answer 1st words differ - expected: '1', found: '584112747'
Subtask #4:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 12ms
memory: 5116kb
input:
96 1005401729
output:
89096525 483840477 71293923 725801219 534609626 858751762 781003182 733870519 679586149 169853826 722428192 634046880 605132083 796185640 40100889 478046380 37336986 596996595 809522335 478547131 844168625 615797976 227576159 72457024 718784103 257732832 692804181 275599076 722231102 399154161 56343...
result:
wrong answer 1st words differ - expected: '1', found: '89096525'
Subtask #5:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 1342ms
memory: 14476kb
input:
496 1005266363
output:
197537203 996130098 30735104 981260329 691271361 827263854 100954357 55589657 925498758 756751804 293297954 73148847 408946477 11780810 439410451 453317081 215460538 849324839 288490525 749012510 780858240 292020014 378979760 831050755 863497708 398943136 672625736 948116119 935336358 284924662 6198...
result:
wrong answer 1st words differ - expected: '1', found: '197537203'