QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#685180#1084. Beautiful Sequence UnravelingRikku_eqAC ✓4020ms8980kbC++142.6kb2024-10-28 18:07:592024-10-28 18:08:00

Judging History

This is the latest submission verdict.

  • [2024-10-28 18:08:00]
  • Judged
  • Verdict: AC
  • Time: 4020ms
  • Memory: 8980kb
  • [2024-10-28 18:07:59]
  • Submitted

answer

#include <bits/stdc++.h>
#define N 405
using namespace std;
typedef long long ll;

int n, K, mod;
ll pre[N], inv[N];
ll g[N][N][3], cur[3], f[N][N], tmp[N];

ll pw (ll bs, ll t)
{
    ll res=1;
    while (t) {
        if (t&1) { res=res*bs%mod; }
        bs=bs*bs%mod; t>>=1;
    }
    return res;
}

ll C (ll x, ll y)
{
    ll res=1;
    for (int i=0; i<y; i++) { res=res*(x-i)%mod; }
    res=res*inv[y] %mod;
    return res;
}

int main ()
{
    // freopen("0test.in", "r", stdin);
    // freopen("0test.out", "w", stdout);

    scanf("%d %d %d", &n, &K, &mod);

    for (int j=1; j<=n; j++) {

        for (int w=1; w<j; w++) {
            ll jw1=pw(j-w+1, mod-2), jw=pw(j-w, mod-2), jw_1=pw(j-w-1, mod-2);
            cur[0]=cur[1]=cur[2]=1;
            for (int k=1; k<=n; k++) {
                (cur[0]*=jw1)%=mod;
                (cur[1]*=jw)%=mod;
                (cur[2]*=jw_1)%=mod;
                for (int tg=0; tg<3; tg++) {
                    g[w][k][tg]=g[w][k-1][tg]+f[w][k]*cur[tg] %mod;
                    g[w][k][tg]%=mod;
                }
            }
        }

        for (int w=1; w<j; w++) {
            cur[0]=cur[1]=cur[2]=1;
            for (int i=1; i<=n; i++) {
                (cur[0]*=(j-w+1))%=mod;
                (cur[1]*=(j-w))%=mod;
                (cur[2]*=(j-w-1))%=mod;
                f[j][i]+=g[w][i-1][0]*cur[0] %mod + mod - 2ll*g[w][i-1][1]*cur[1] %mod + g[w][i-1][2]*cur[2] %mod;
                f[j][i]%=mod;
            }
        }

        ll pwj=1, pwj1=1, sum=0;
        for (int i=1; i<=n; i++) {
            pwj=pwj*j %mod; pwj1=pwj1*(mod-1+j) %mod;
            f[j][i]=mod-f[j][i];
            f[j][i]+=pwj+(mod-pwj1)+(mod-sum); f[j][i]%=mod;
            sum=(sum+f[j][i])%mod;

            if (i!=n) {
                for (int k=j; k<=n; k++) {
                    tmp[k]+=mod- f[j][i]*(pw(k-j+1, n-i)+mod-pw(k-j, n-i)) %mod;
                    tmp[k]%=mod;
                }
            }
        }
    }

    pre[0]=1; for (int i=1; i<=n; i++) { pre[i]=pre[i-1]*(ll)i %mod; }
    inv[n]=pw(pre[n], mod-2);
    for (int i=n-1; i>=0; i--) { inv[i]=inv[i+1]*(ll)(i+1) %mod; }

    // for (int i=1; i<=n; i++) { cout<<tmp[i]<<" "; } cout<<endl;

    for (int i=1; i<=n; i++) { tmp[i]+=pw(i, n); tmp[i]%=mod; }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<i; j++) {
            tmp[i]+=mod-tmp[j]*pre[i] %mod *inv[j] %mod *inv[i-j]%mod; tmp[i]%=mod;
        }
    }

    ll ans=0;
    for (int i=1; i<=n; i++) {
        (tmp[i]*=C(K, i))%=mod; ans+=tmp[i]; ans%=mod;
    }
    printf("%lld\n", ans);

    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3892kb

input:

2 2 1000000007

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

3 4 1000000009

output:

36

result:

ok 1 number(s): "36"

Test #3:

score: 0
Accepted
time: 709ms
memory: 7708kb

input:

228 112263 998244353

output:

379700769

result:

ok 1 number(s): "379700769"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

1 1 998595277

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

2 2 998683811

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

3 1 998277223

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

4 1 998365733

output:

0

result:

ok 1 number(s): "0"

Test #8:

score: 0
Accepted
time: 4020ms
memory: 8888kb

input:

400 100000000 998244353

output:

318973800

result:

ok 1 number(s): "318973800"

Test #9:

score: 0
Accepted
time: 4005ms
memory: 8884kb

input:

400 1 1000000007

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

2 9 999603883

output:

72

result:

ok 1 number(s): "72"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

1 1 998784541

output:

1

result:

ok 1 number(s): "1"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

3 3 999209353

output:

12

result:

ok 1 number(s): "12"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

4 12 999787531

output:

16544

result:

ok 1 number(s): "16544"

Test #14:

score: 0
Accepted
time: 4002ms
memory: 8892kb

input:

400 3 998785127

output:

505031599

result:

ok 1 number(s): "505031599"

Test #15:

score: 0
Accepted
time: 4013ms
memory: 8876kb

input:

400 77 999400643

output:

877578741

result:

ok 1 number(s): "877578741"

Test #16:

score: 0
Accepted
time: 4008ms
memory: 8952kb

input:

400 374 998458939

output:

202865317

result:

ok 1 number(s): "202865317"

Test #17:

score: 0
Accepted
time: 4013ms
memory: 8952kb

input:

400 77435643 999245677

output:

833344996

result:

ok 1 number(s): "833344996"

Test #18:

score: 0
Accepted
time: 3982ms
memory: 8888kb

input:

399 72119824 999010279

output:

188282648

result:

ok 1 number(s): "188282648"

Test #19:

score: 0
Accepted
time: 3954ms
memory: 8892kb

input:

398 22521432 999827603

output:

986913334

result:

ok 1 number(s): "986913334"

Test #20:

score: 0
Accepted
time: 3921ms
memory: 8980kb

input:

397 77955743 998803427

output:

32764673

result:

ok 1 number(s): "32764673"