QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#32650 | #1084. Beautiful Sequence Unraveling | Wu_Ren | AC ✓ | 1214ms | 7064kb | C++17 | 1.2kb | 2022-05-22 20:24:32 | 2022-05-22 20:24:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int mod;
int n,K,inv[410][410],_k[410][410],g[410][410],f[410][410],h[410],C[410][410];
void qmo(int &x){
x+=(x>>31)&mod;
}
void init(int N){
inv[1][1]=1;
for(int i=2;i<=N;i++) inv[i][1]=mod-1ll*(mod/i)*inv[mod%i][1]%mod;
for(int i=1;i<=N;i++){
inv[i][0]=_k[i][0]=1,_k[i][1]=i;
for(int j=2;j<=N;j++){
inv[i][j]=1ll*inv[i][j-1]*inv[i][1]%mod;//i^{-j}
_k[i][j]=1ll*_k[i][j-1]*i%mod;//i^j
}
}
for(int i=0;i<=N;i++) for(int j=C[i][0]=1;j<=i;j++) qmo(C[i][j]=C[i-1][j-1]+C[i-1][j]-mod);
}
int main(){
scanf("%d%d%d",&n,&K,&mod),init(n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
f[i][j]=_k[j][i];
for(int y=1;y<=j;y++){
f[i][j]=(f[i][j]-1ll*_k[y][i]*(g[j-y+1][y]-g[j-y][y]+mod)%mod+mod+1ll*_k[y-1][i]*(g[j-y+1][y-1]-g[j-y][y-1]+mod))%mod;
}
// printf("f[%d][%d]=%d\n",i,j,f[i][j]);
}
for(int j=1;j<=n;j++) for(int y=1;y<=n;y++) g[j][y]=(g[j][y]+1ll*f[i][j]*inv[y][i])%mod;
}
int CK=1,ans=0;
for(int i=1;i<=n;i++){
CK=1ll*CK*(K-i+1)%mod*inv[i][1]%mod;
h[i]=f[n][i];
for(int j=1;j<i;j++) qmo(h[i]-=1ll*h[j]*C[i][j]%mod);
ans=(ans+1ll*h[i]*CK)%mod;
}
printf("%d\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3812kb
input:
2 2 1000000007
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 3ms
memory: 5832kb
input:
3 4 1000000009
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 220ms
memory: 5628kb
input:
228 112263 998244353
output:
379700769
result:
ok 1 number(s): "379700769"
Test #4:
score: 0
Accepted
time: 0ms
memory: 5844kb
input:
1 1 998595277
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
2 2 998683811
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 3ms
memory: 3708kb
input:
3 1 998277223
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 3ms
memory: 3772kb
input:
4 1 998365733
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 1168ms
memory: 6996kb
input:
400 100000000 998244353
output:
318973800
result:
ok 1 number(s): "318973800"
Test #9:
score: 0
Accepted
time: 1173ms
memory: 6952kb
input:
400 1 1000000007
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
2 9 999603883
output:
72
result:
ok 1 number(s): "72"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
1 1 998784541
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 3ms
memory: 5852kb
input:
3 3 999209353
output:
12
result:
ok 1 number(s): "12"
Test #13:
score: 0
Accepted
time: 3ms
memory: 5820kb
input:
4 12 999787531
output:
16544
result:
ok 1 number(s): "16544"
Test #14:
score: 0
Accepted
time: 1214ms
memory: 6876kb
input:
400 3 998785127
output:
505031599
result:
ok 1 number(s): "505031599"
Test #15:
score: 0
Accepted
time: 1171ms
memory: 6988kb
input:
400 77 999400643
output:
877578741
result:
ok 1 number(s): "877578741"
Test #16:
score: 0
Accepted
time: 1174ms
memory: 6996kb
input:
400 374 998458939
output:
202865317
result:
ok 1 number(s): "202865317"
Test #17:
score: 0
Accepted
time: 1178ms
memory: 7064kb
input:
400 77435643 999245677
output:
833344996
result:
ok 1 number(s): "833344996"
Test #18:
score: 0
Accepted
time: 1168ms
memory: 6960kb
input:
399 72119824 999010279
output:
188282648
result:
ok 1 number(s): "188282648"
Test #19:
score: 0
Accepted
time: 1156ms
memory: 6972kb
input:
398 22521432 999827603
output:
986913334
result:
ok 1 number(s): "986913334"
Test #20:
score: 0
Accepted
time: 1154ms
memory: 6864kb
input:
397 77955743 998803427
output:
32764673
result:
ok 1 number(s): "32764673"