QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#360506 | #1084. Beautiful Sequence Unraveling | SolitaryDream# | AC ✓ | 763ms | 16372kb | C++17 | 2.9kb | 2024-03-21 20:39:54 | 2024-03-21 20:39:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long long ll;
const int N=405;
int Mod;
ll Fast(ll x,int b) {
ll t=1;
for(; b; b>>=1,x=x*x%Mod) if(b&1) t=t*x%Mod;
return t;
}
ll f[2][N][N][2][2];
ll h[N][N][2];
void add(ll &x,ll y) {
x=(x+y)%Mod;
}
ll g[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,K;
cin >> n >> K >> Mod;
h[0][0][0]=1;
int cur=0;
FOR(i,0,n-1) {
memset(f[cur],0,sizeof(f[cur]));
cur^=1;
if(i>0) {
FOR(j,0,i) FOR(k,0,j) {
FOR(u,0,1) FOR(v,0,1) {
ll w=f[cur][j][k][u][v];
if(!w) continue;
if(u && v) {
// cerr << i << ' ' << j << ' ' << w << endl;
add(f[cur][j][1][0][0],-w);
}
}
}
FOR(j,0,i) {
FOR(v,0,1) {
if(v) {
add(f[cur][j][1][0][0],-h[i][j][v]);
}
}
}
}
FOR(j,0,i) FOR(v,0,1) {
ll w=h[i][j][v];
if(!w) continue;
if(j==1) {
add(h[i+1][j][0],w);
} else if(j>=2) {
add(h[i+1][j][1],w);
add(h[i+1][j][1],w*(j-2));
add(h[i+1][j][0],w);
}
add(h[i+1][j+1][1],w*(j+1));
}
FOR(j,0,i) FOR(k,0,j) {
FOR(u,0,1) FOR(v,0,1) {
ll w=f[cur][j][k][u][v];
// if(i==1 && j==1 && k==1 && u==0 && v==0) cerr << w << endl;
if(!w) continue;
if(k==1) {
add(f[cur^1][j][k][1][0],w);
} else if(k>=2) {
add(f[cur^1][j][k][1][1],w);
add(f[cur^1][j][k][u][1],w*(k-2));
add(f[cur^1][j][k][u][0],w);
}
if(k==0) {
// if(i==0 && j==0 && k==0) cerr << u << ' ' << w << endl;
add(f[cur^1][j+1][k+1][u][1],w);
} else {
add(f[cur^1][j+1][k+1][u][1],w*(k-1));
add(f[cur^1][j+1][k+1][u][1],w);
}
}
}
}
// cerr << f[1][1][1][1][1] << endl;
FOR(j,0,n) {
g[j]=1;
FOR(k,1,j) {
g[j]=g[j]*Fast(k,Mod-2)%Mod;
g[j]=g[j]*(K-k+1)%Mod;
}
}
ll res=0;
cur^=1;
FOR(j,0,n) FOR(k,0,j) FOR(u,1,1) FOR(v,0,1) {
ll w=f[cur][j][k][u][v];
if(!w) continue;
add(res,g[j]*w);
}
FOR(j,0,n) FOR(v,0,1) {
add(res,g[j]*h[n][j][v]);
}
if(res<0) res+=Mod;
cout << res << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 15652kb
input:
2 2 1000000007
output:
2
result:
ok 1 number(s): "2"
Test #2:
score: 0
Accepted
time: 3ms
memory: 14028kb
input:
3 4 1000000009
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 170ms
memory: 15480kb
input:
228 112263 998244353
output:
379700769
result:
ok 1 number(s): "379700769"
Test #4:
score: 0
Accepted
time: 2ms
memory: 9764kb
input:
1 1 998595277
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 15924kb
input:
2 2 998683811
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 2ms
memory: 14640kb
input:
3 1 998277223
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 2ms
memory: 14344kb
input:
4 1 998365733
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 761ms
memory: 16340kb
input:
400 100000000 998244353
output:
318973800
result:
ok 1 number(s): "318973800"
Test #9:
score: 0
Accepted
time: 759ms
memory: 16248kb
input:
400 1 1000000007
output:
0
result:
ok 1 number(s): "0"
Test #10:
score: 0
Accepted
time: 0ms
memory: 15364kb
input:
2 9 999603883
output:
72
result:
ok 1 number(s): "72"
Test #11:
score: 0
Accepted
time: 1ms
memory: 9824kb
input:
1 1 998784541
output:
1
result:
ok 1 number(s): "1"
Test #12:
score: 0
Accepted
time: 2ms
memory: 14244kb
input:
3 3 999209353
output:
12
result:
ok 1 number(s): "12"
Test #13:
score: 0
Accepted
time: 0ms
memory: 15632kb
input:
4 12 999787531
output:
16544
result:
ok 1 number(s): "16544"
Test #14:
score: 0
Accepted
time: 763ms
memory: 16296kb
input:
400 3 998785127
output:
505031599
result:
ok 1 number(s): "505031599"
Test #15:
score: 0
Accepted
time: 758ms
memory: 16296kb
input:
400 77 999400643
output:
877578741
result:
ok 1 number(s): "877578741"
Test #16:
score: 0
Accepted
time: 759ms
memory: 16324kb
input:
400 374 998458939
output:
202865317
result:
ok 1 number(s): "202865317"
Test #17:
score: 0
Accepted
time: 760ms
memory: 16372kb
input:
400 77435643 999245677
output:
833344996
result:
ok 1 number(s): "833344996"
Test #18:
score: 0
Accepted
time: 755ms
memory: 16336kb
input:
399 72119824 999010279
output:
188282648
result:
ok 1 number(s): "188282648"
Test #19:
score: 0
Accepted
time: 744ms
memory: 16248kb
input:
398 22521432 999827603
output:
986913334
result:
ok 1 number(s): "986913334"
Test #20:
score: 0
Accepted
time: 748ms
memory: 16296kb
input:
397 77955743 998803427
output:
32764673
result:
ok 1 number(s): "32764673"