QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#888078 | #1084. Beautiful Sequence Unraveling | qwqUwU_ | AC ✓ | 262ms | 4864kb | C++14 | 1.0kb | 2025-02-07 21:55:58 | 2025-02-07 21:55:58 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
int mod;
inline int fp(int x,int p=mod-2,int res=1){
for(;p;p>>=1){if(p&1)res=1ll*res*x%mod;x=1ll*x*x%mod;}
return res;
}
inline void Ad(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void Mi(int &x,int y){x=x-y<0?x-y+mod:x-y;}
const int N=402;
int n,K,f[N][N],C[N][N],g[N],c[N];
int main() {
cin>>n>>K>>mod;
rep(i,0,n){
C[i][0]=1;
rep(j,1,i)Ad(C[i][j]=C[i-1][j],C[i-1][j-1]);
}
rep(j,1,n){
f[j][1]=j;
rep(i,2,n)f[j][i]=1ll*f[j][i-1]*j%mod;
per(k,j,1){
int a[2];
rep(d,0,1)a[d]=0;
rep(i,1,n){
Ad(f[j][i],a[1]),Mi(f[j][i],a[0]);
rep(d,0,1)a[d]=1ll*(k-d)*(1ll*a[d]+f[j-k+1][i]-f[j-k][i]+mod)%mod;
}
}
}
rep(j,1,n){
g[j]=f[j][n];
rep(i,1,j-1)Mi(g[j],1ll*C[j][i]*g[i]%mod);
}
c[0]=1;
rep(i,1,n)c[i]=1ll*c[i-1]*fp(i)%mod*(K-i+1)%mod;
int ans=0;
rep(i,1,n)Ad(ans,1ll*c[i]*g[i]%mod);
cout<<ans;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3456kb
input:
2 2 1000000007
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
3 4 1000000009
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 49ms
memory: 4096kb
input:
228 112263 998244353
output:
379700769
result:
ok 1 number(s): "379700769"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 1 998595277
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 2 998683811
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 1 998277223
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
4 1 998365733
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 262ms
memory: 4608kb
input:
400 100000000 998244353
output:
318973800
result:
ok 1 number(s): "318973800"
Test #9:
score: 0
Accepted
time: 262ms
memory: 4608kb
input:
400 1 1000000007
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
2 9 999603883
output:
72
result:
ok 1 number(s): "72"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 1 998784541
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
3 3 999209353
output:
12
result:
ok 1 number(s): "12"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3328kb
input:
4 12 999787531
output:
16544
result:
ok 1 number(s): "16544"
Test #14:
score: 0
Accepted
time: 261ms
memory: 4736kb
input:
400 3 998785127
output:
505031599
result:
ok 1 number(s): "505031599"
Test #15:
score: 0
Accepted
time: 261ms
memory: 4736kb
input:
400 77 999400643
output:
877578741
result:
ok 1 number(s): "877578741"
Test #16:
score: 0
Accepted
time: 261ms
memory: 4608kb
input:
400 374 998458939
output:
202865317
result:
ok 1 number(s): "202865317"
Test #17:
score: 0
Accepted
time: 259ms
memory: 4608kb
input:
400 77435643 999245677
output:
833344996
result:
ok 1 number(s): "833344996"
Test #18:
score: 0
Accepted
time: 260ms
memory: 4864kb
input:
399 72119824 999010279
output:
188282648
result:
ok 1 number(s): "188282648"
Test #19:
score: 0
Accepted
time: 257ms
memory: 4864kb
input:
398 22521432 999827603
output:
986913334
result:
ok 1 number(s): "986913334"
Test #20:
score: 0
Accepted
time: 255ms
memory: 4736kb
input:
397 77955743 998803427
output:
32764673
result:
ok 1 number(s): "32764673"