QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#360506#1084. Beautiful Sequence UnravelingSolitaryDream#AC ✓763ms16372kbC++172.9kb2024-03-21 20:39:542024-03-21 20:39:55

Judging History

This is the latest submission verdict.

  • [2024-03-21 20:39:55]
  • Judged
  • Verdict: AC
  • Time: 763ms
  • Memory: 16372kb
  • [2024-03-21 20:39:54]
  • Submitted

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"