QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#775766#9782. NonZero PrefSuf Sumsucup-team138#AC ✓211ms9032kbC++174.3kb2024-11-23 16:38:412024-11-23 16:38:42

Judging History

This is the latest submission verdict.

  • [2024-11-23 16:38:42]
  • Judged
  • Verdict: AC
  • Time: 211ms
  • Memory: 9032kb
Show
  • [2024-11-23 16:38:41]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int mod,n,m;
int C[110][110];
void update(int &x,int y) { x+=y; if (x>=mod) x-=mod; }
int ans;
int ksm(int x,int y) {
    int res=1;
    while (y) {
        if (y&1) res=(ll)res*x%mod;
        x=(ll)x*x%mod; y>>=1;
    }
    return res;
}
const int N=100*100;
int f[2][110*110*2],s[110*110*2];
int ivjc[110],jc[110];
int dp[2][110][110],bd[110],suf[110];
int dp2[110][110][110];
int main() {
    scanf("%d %d",&n,&m);
    scanf("%d",&mod);
    ivjc[0]=jc[0]=1;
    for (int i=1;i<=100;i++) {
        jc[i]=(ll)jc[i-1]*i%mod;
        ivjc[i]=ksm(jc[i],mod-2);
    }
    for (int i=0;i<=n;i++) {
        C[i][0]=C[i][i]=1;
        for (int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    int all=ksm(m*2+1,n);
    f[0][N]=1;
    for (int i=1;i<=n;i++) {
        memset(f[i&1],0,sizeof(f[i&1^1]));
        memset(s,0,sizeof(s));
        for (int j=-(i-1)*m;j<=(i-1)*m;++j) {
            update(s[j+N-m],f[i&1^1][j+N]);
            update(s[j+N+m+1],mod-f[i&1^1][j+N]);
        }
        for (int j=-i*m;j<=i*m;++j) {
            update(s[j+N],s[j+N-1]);
            f[i&1][j+N]=s[j+N];
        }
    }
    ans=f[n&1][N];
    // printf("%d %d\n",all,ans);
    // a * x
    // #=(n-a), sum<a, 0<=single<=m/x
    // one single >= a-sum-1
    for (int x=1;x<=m;++x) bd[m/x]++;
    for (int a=1;a<n;++a) {
        for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) dp[0][cnt][sum]=0;
        dp[0][0][0]=1;
        int op=0;
        for (int i=0;i<=m;++i) {
            for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) dp[op^1][cnt][sum]=0;
            for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) if (dp[op][cnt][sum])
                for (int nxt=0;nxt*i+sum<a&&nxt+cnt<=n-a;nxt++) {
                    update(dp[op^1][cnt+nxt][nxt*i+sum],(ll)dp[op][cnt][sum]*ivjc[nxt]%mod);
                }
            op^=1;
            int tmp=0;
            for (int sum=0;sum<a;++sum) update(tmp,dp[op][n-a][sum]);
            tmp=(ll)tmp*jc[n-a]%mod*C[n][a]%mod;
            update(ans,(ll)tmp*bd[i]%mod*2%mod);
        }
    }
    for (int a=1;a<n;++a) {
        int tmp=0,tt=(ll)jc[n-a]*C[n][a]%mod;
        int flag=0;
        for (int S=0;S<a;++S) {
            if (S<=a-4) {
                memset(bd,0,sizeof(bd));
                for (int x=1;x<=m;++x) bd[min(a-S-2,m/x)]++;
                for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) dp2[0][cnt][sum]=0;
                dp2[0][0][0]=1;
                if (!flag) {
                    for (int i=0;i<a-S-1;++i) {
                        for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) dp2[i+1][cnt][sum]=0;
                        for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) if (dp2[i][cnt][sum])
                            for (int nxt=0;nxt*i+sum<a&&nxt+cnt<=n-a;++nxt) {
                                update(dp2[i+1][cnt+nxt][nxt*i+sum],(ll)dp2[i][cnt][sum]*ivjc[nxt]%mod);
                            }
                    }
                    flag=1;
                }
                for (int i=0;i<a-S-1;++i) update(ans,mod-(ll)dp2[i+1][n-a][S]*tt%mod*2%mod*bd[i]%mod);
            } else {
                for (int x=1;x<=m;++x) {
                    for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) dp[0][cnt][sum]=0;
                    dp[0][0][0]=1;
                    int op=0;
                    for (int i=0;i<a-S-1&&i<=m/x;++i) {
                        for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) dp[op^1][cnt][sum]=0;
                        for (int cnt=0;cnt<=n-a;++cnt) for (int sum=0;sum<a;++sum) if (dp[op][cnt][sum])
                            for (int nxt=0;nxt*i+sum<a&&nxt+cnt<=n-a;++nxt) {
                                update(dp[op^1][cnt+nxt][nxt*i+sum],(ll)dp[op][cnt][sum]*ivjc[nxt]%mod);
                            }
                        op^=1;
                    }
                    int coef=(ll)dp[op][n-a][S]*tt%mod;
                    update(ans,mod-coef*2%mod);
                }
            }
            // update(tmp,dp[op][n-a][S]);
            // for (int sum=0;sum<a;sum++) update(tmp,dp[op][n-a][sum]);
        }
    }
    ans=(all-ans+mod)%mod;
    printf("%d\n",ans);
    return 0;
}
源文件, 语言: C++17

詳細信息

Test #1:

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

input:

2 1 998244353

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 40ms
memory: 9032kb

input:

69 42 696969697

output:

378553557

result:

ok single line: '378553557'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4208kb

input:

2 1 998244353

output:

2

result:

ok single line: '2'

Test #4:

score: 0
Accepted
time: 37ms
memory: 7292kb

input:

69 42 696969697

output:

378553557

result:

ok single line: '378553557'

Test #5:

score: 0
Accepted
time: 38ms
memory: 7112kb

input:

61 75 677323601

output:

34613998

result:

ok single line: '34613998'

Test #6:

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

input:

13 14 670577333

output:

41465431

result:

ok single line: '41465431'

Test #7:

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

input:

14 6 987686347

output:

37536510

result:

ok single line: '37536510'

Test #8:

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

input:

15 12 196428923

output:

29322522

result:

ok single line: '29322522'

Test #9:

score: 0
Accepted
time: 18ms
memory: 8924kb

input:

68 7 786815587

output:

149281835

result:

ok single line: '149281835'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4180kb

input:

3 2 503002109

output:

82

result:

ok single line: '82'

Test #11:

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

input:

13 5 756093197

output:

415698676

result:

ok single line: '415698676'

Test #12:

score: 0
Accepted
time: 1ms
memory: 4208kb

input:

2 3 646574611

output:

30

result:

ok single line: '30'

Test #13:

score: 0
Accepted
time: 11ms
memory: 6716kb

input:

39 68 120037189

output:

43217507

result:

ok single line: '43217507'

Test #14:

score: 0
Accepted
time: 1ms
memory: 6212kb

input:

13 4 423132517

output:

360231790

result:

ok single line: '360231790'

Test #15:

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

input:

14 3 309713387

output:

94215386

result:

ok single line: '94215386'

Test #16:

score: 0
Accepted
time: 4ms
memory: 4412kb

input:

24 77 886983941

output:

211636479

result:

ok single line: '211636479'

Test #17:

score: 0
Accepted
time: 1ms
memory: 5968kb

input:

3 3 504388063

output:

270

result:

ok single line: '270'

Test #18:

score: 0
Accepted
time: 1ms
memory: 6244kb

input:

3 1 936205423

output:

8

result:

ok single line: '8'

Test #19:

score: 0
Accepted
time: 1ms
memory: 6216kb

input:

3 3 295983139

output:

270

result:

ok single line: '270'

Test #20:

score: 0
Accepted
time: 1ms
memory: 6256kb

input:

10 15 446169107

output:

149884328

result:

ok single line: '149884328'

Test #21:

score: 0
Accepted
time: 5ms
memory: 4720kb

input:

37 18 833753929

output:

592917251

result:

ok single line: '592917251'

Test #22:

score: 0
Accepted
time: 1ms
memory: 6240kb

input:

11 3 998773403

output:

860630017

result:

ok single line: '860630017'

Test #23:

score: 0
Accepted
time: 2ms
memory: 6244kb

input:

14 85 688036639

output:

347188409

result:

ok single line: '347188409'

Test #24:

score: 0
Accepted
time: 1ms
memory: 4060kb

input:

3 3 844621907

output:

270

result:

ok single line: '270'

Test #25:

score: 0
Accepted
time: 1ms
memory: 4036kb

input:

3 4 204335891

output:

620

result:

ok single line: '620'

Test #26:

score: 0
Accepted
time: 1ms
memory: 4144kb

input:

7 8 113007667

output:

58946097

result:

ok single line: '58946097'

Test #27:

score: 0
Accepted
time: 1ms
memory: 4200kb

input:

4 1 637268377

output:

22

result:

ok single line: '22'

Test #28:

score: 0
Accepted
time: 1ms
memory: 6268kb

input:

11 14 391637237

output:

303270280

result:

ok single line: '303270280'

Test #29:

score: 0
Accepted
time: 1ms
memory: 4248kb

input:

3 2 208286231

output:

82

result:

ok single line: '82'

Test #30:

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

input:

2 11 662696483

output:

462

result:

ok single line: '462'

Test #31:

score: 0
Accepted
time: 3ms
memory: 6348kb

input:

19 55 974135299

output:

887460557

result:

ok single line: '887460557'

Test #32:

score: 0
Accepted
time: 1ms
memory: 4120kb

input:

6 8 417027509

output:

23351024

result:

ok single line: '23351024'

Test #33:

score: 0
Accepted
time: 1ms
memory: 4092kb

input:

8 13 624006587

output:

353008442

result:

ok single line: '353008442'

Test #34:

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

input:

10 10 740294671

output:

79436611

result:

ok single line: '79436611'

Test #35:

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

input:

11 10 394088657

output:

161476458

result:

ok single line: '161476458'

Test #36:

score: 0
Accepted
time: 1ms
memory: 4220kb

input:

9 27 562853573

output:

135252259

result:

ok single line: '135252259'

Test #37:

score: 0
Accepted
time: 1ms
memory: 4216kb

input:

8 3 829129009

output:

5349034

result:

ok single line: '5349034'

Test #38:

score: 0
Accepted
time: 18ms
memory: 6900kb

input:

51 49 924010279

output:

815049368

result:

ok single line: '815049368'

Test #39:

score: 0
Accepted
time: 1ms
memory: 6288kb

input:

12 2 308466749

output:

223013998

result:

ok single line: '223013998'

Test #40:

score: 0
Accepted
time: 1ms
memory: 4064kb

input:

7 4 567557693

output:

4502296

result:

ok single line: '4502296'

Test #41:

score: 0
Accepted
time: 8ms
memory: 8504kb

input:

36 93 943780729

output:

13599465

result:

ok single line: '13599465'

Test #42:

score: 0
Accepted
time: 1ms
memory: 6164kb

input:

2 1 828681127

output:

2

result:

ok single line: '2'

Test #43:

score: 0
Accepted
time: 1ms
memory: 4176kb

input:

3 3 534160729

output:

270

result:

ok single line: '270'

Test #44:

score: 0
Accepted
time: 1ms
memory: 4204kb

input:

7 12 920925433

output:

453086694

result:

ok single line: '453086694'

Test #45:

score: 0
Accepted
time: 1ms
memory: 4200kb

input:

3 2 440546987

output:

82

result:

ok single line: '82'

Test #46:

score: 0
Accepted
time: 51ms
memory: 8944kb

input:

90 9 291269963

output:

72560304

result:

ok single line: '72560304'

Test #47:

score: 0
Accepted
time: 4ms
memory: 6572kb

input:

38 10 867575113

output:

165530481

result:

ok single line: '165530481'

Test #48:

score: 0
Accepted
time: 12ms
memory: 6516kb

input:

48 37 152663531

output:

135425620

result:

ok single line: '135425620'

Test #49:

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

input:

15 15 991731803

output:

102703562

result:

ok single line: '102703562'

Test #50:

score: 0
Accepted
time: 211ms
memory: 7964kb

input:

100 100 696969697

output:

313377809

result:

ok single line: '313377809'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

伺服器時間: 2025-03-13 16:30:43 | 開源專案