QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#50176#4807. Melborp Lacissalcsealnot123#AC ✓392ms56488kbC++1.5kb2022-09-25 02:23:122022-09-25 02:23:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-25 02:23:13]
  • 评测
  • 测评结果:AC
  • 用时:392ms
  • 内存:56488kb
  • [2022-09-25 02:23:12]
  • 提交

answer

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back

#define rep(i,a,b) for(int i=a; i<(b); ++i)
#define FOR(i,a,b) for(int i=a; i<=(b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int mod = 998244353;
const int N = 66;
int dp[N][N][N*N];
int fac[N], cnr[N][N];

int mul(int a, int b) {
    return a*1ll*b%mod;
}
int add(int a, int b) {
    return (a+=b)>=mod? a-mod:a;
}

void adding(int &a, int b) {
    a = add(a,b);
}

void solve() {
    fac[0] = 1;
    cnr[0][0] = 1;
    FOR(i, 1, N-1) {
        fac[i] = mul(fac[i-1],i);
        cnr[i][0] = 1;
        FOR(j, 1, i) {
            cnr[i][j] = add(cnr[i-1][j-1], cnr[i-1][j]);
            //printf("(%d,%d) = %d\n",i,j,cnr[i][j]);
        }
    }

    int n, k, t;
    scanf("%d %d %d",&n,&k,&t);
    // initialize
    FOR(j, 0, n) {
        dp[0][j][j*(j+1)/2] = cnr[n][j];
    }

    // dp
    FOR(i, 1, k-1) {
        FOR(j, 0, n) {
            FOR(l, 0, n) {
                if(j+l > n) break;
                FOR(m, 0, n*(n+1)/2) {
                    if(m+l*(l-1)/2 > n*(n+1)/2) break;
                    adding(dp[i][j+l][m+l*(l-1)/2], mul(dp[i-1][j][m], cnr[n-j][l]));
                }
            }
        }
    }

    printf("%d",dp[k-1][n][t]);
}

int main() {
    solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 7872kb

input:

2 5 1

output:

12

result:

ok 1 number(s): "12"

Test #2:

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

input:

7 10 15

output:

2016

result:

ok 1 number(s): "2016"

Test #3:

score: 0
Accepted
time: 88ms
memory: 28208kb

input:

46 50 171

output:

645560469

result:

ok 1 number(s): "645560469"

Test #4:

score: 0
Accepted
time: 375ms
memory: 56100kb

input:

64 64 0

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 392ms
memory: 56256kb

input:

64 64 1

output:

326126263

result:

ok 1 number(s): "326126263"

Test #6:

score: 0
Accepted
time: 345ms
memory: 54640kb

input:

63 64 0

output:

4476118

result:

ok 1 number(s): "4476118"

Test #7:

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

input:

11 45 14

output:

963276342

result:

ok 1 number(s): "963276342"

Test #8:

score: 0
Accepted
time: 16ms
memory: 14716kb

input:

35 20 565

output:

0

result:

ok 1 number(s): "0"

Test #9:

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

input:

3 64 5

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 28ms
memory: 20708kb

input:

35 45 153

output:

181934997

result:

ok 1 number(s): "181934997"

Test #11:

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

input:

3 25 5

output:

0

result:

ok 1 number(s): "0"

Test #12:

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

input:

35 5 373

output:

740122840

result:

ok 1 number(s): "740122840"

Test #13:

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

input:

3 50 5

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 24ms
memory: 17092kb

input:

35 30 592

output:

0

result:

ok 1 number(s): "0"

Test #15:

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

input:

3 11 1

output:

540

result:

ok 1 number(s): "540"

Test #16:

score: 0
Accepted
time: 29ms
memory: 22876kb

input:

35 55 352

output:

656633208

result:

ok 1 number(s): "656633208"

Test #17:

score: 0
Accepted
time: 115ms
memory: 28452kb

input:

54 38 356

output:

215089708

result:

ok 1 number(s): "215089708"

Test #18:

score: 0
Accepted
time: 7ms
memory: 13292kb

input:

22 19 189

output:

0

result:

ok 1 number(s): "0"

Test #19:

score: 0
Accepted
time: 208ms
memory: 41636kb

input:

54 63 401

output:

987604839

result:

ok 1 number(s): "987604839"

Test #20:

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

input:

22 43 171

output:

827743481

result:

ok 1 number(s): "827743481"

Test #21:

score: 0
Accepted
time: 76ms
memory: 20552kb

input:

54 24 446

output:

551546514

result:

ok 1 number(s): "551546514"

Test #22:

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

input:

22 4 152

output:

0

result:

ok 1 number(s): "0"

Test #23:

score: 0
Accepted
time: 148ms
memory: 33712kb

input:

54 48 1306

output:

0

result:

ok 1 number(s): "0"

Test #24:

score: 0
Accepted
time: 6ms
memory: 14356kb

input:

22 29 7

output:

374430631

result:

ok 1 number(s): "374430631"

Test #25:

score: 0
Accepted
time: 29ms
memory: 12724kb

input:

54 9 1351

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

22 54 5

output:

267958047

result:

ok 1 number(s): "267958047"

Test #27:

score: 0
Accepted
time: 189ms
memory: 30936kb

input:

64 32 1315

output:

494251101

result:

ok 1 number(s): "494251101"

Test #28:

score: 0
Accepted
time: 10ms
memory: 12820kb

input:

33 12 332

output:

765350074

result:

ok 1 number(s): "765350074"

Test #29:

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

input:

1 57 1

output:

1

result:

ok 1 number(s): "1"

Test #30:

score: 0
Accepted
time: 21ms
memory: 18152kb

input:

33 37 363

output:

0

result:

ok 1 number(s): "0"

Test #31:

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

input:

1 17 0

output:

16

result:

ok 1 number(s): "16"

Test #32:

score: 0
Accepted
time: 34ms
memory: 23416kb

input:

33 62 148

output:

871819399

result:

ok 1 number(s): "871819399"

Test #33:

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

input:

1 42 0

output:

41

result:

ok 1 number(s): "41"

Test #34:

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

input:

33 23 179

output:

23699248

result:

ok 1 number(s): "23699248"

Test #35:

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

input:

1 3 1

output:

1

result:

ok 1 number(s): "1"

Test #36:

score: 0
Accepted
time: 25ms
memory: 20264kb

input:

33 47 211

output:

267909794

result:

ok 1 number(s): "267909794"

Test #37:

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

input:

11 26 32

output:

0

result:

ok 1 number(s): "0"

Test #38:

score: 0
Accepted
time: 9ms
memory: 9976kb

input:

43 6 579

output:

280289125

result:

ok 1 number(s): "280289125"

Test #39:

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

input:

11 50 5

output:

865381083

result:

ok 1 number(s): "865381083"

Test #40:

score: 0
Accepted
time: 35ms
memory: 19840kb

input:

43 31 750

output:

0

result:

ok 1 number(s): "0"

Test #41:

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

input:

11 11 12

output:

753565341

result:

ok 1 number(s): "753565341"

Test #42:

score: 0
Accepted
time: 87ms
memory: 28220kb

input:

43 56 290

output:

575236094

result:

ok 1 number(s): "575236094"

Test #43:

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

input:

11 36 52

output:

0

result:

ok 1 number(s): "0"

Test #44:

score: 0
Accepted
time: 22ms
memory: 14900kb

input:

44 16 0

output:

0

result:

ok 1 number(s): "0"

Test #45:

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

input:

12 61 31

output:

682427534

result:

ok 1 number(s): "682427534"

Test #46:

score: 0
Accepted
time: 55ms
memory: 23816kb

input:

44 41 365

output:

759457870

result:

ok 1 number(s): "759457870"

Test #47:

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

input:

22 19 70

output:

247296498

result:

ok 1 number(s): "247296498"

Test #48:

score: 0
Accepted
time: 202ms
memory: 42344kb

input:

54 64 444

output:

418216086

result:

ok 1 number(s): "418216086"

Test #49:

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

input:

22 44 52

output:

779702126

result:

ok 1 number(s): "779702126"

Test #50:

score: 0
Accepted
time: 85ms
memory: 21184kb

input:

54 25 1303

output:

0

result:

ok 1 number(s): "0"

Test #51:

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

input:

22 5 49

output:

219556981

result:

ok 1 number(s): "219556981"

Test #52:

score: 0
Accepted
time: 156ms
memory: 34204kb

input:

54 49 1269

output:

0

result:

ok 1 number(s): "0"

Test #53:

score: 0
Accepted
time: 6ms
memory: 14424kb

input:

22 30 14

output:

719775605

result:

ok 1 number(s): "719775605"

Test #54:

score: 0
Accepted
time: 24ms
memory: 13368kb

input:

54 10 1314

output:

0

result:

ok 1 number(s): "0"

Test #55:

score: 0
Accepted
time: 7ms
memory: 17208kb

input:

22 54 12

output:

325137058

result:

ok 1 number(s): "325137058"

Test #56:

score: 0
Accepted
time: 110ms
memory: 26684kb

input:

54 35 1359

output:

0

result:

ok 1 number(s): "0"

Test #57:

score: 0
Accepted
time: 7ms
memory: 13092kb

input:

33 13 335

output:

202725820

result:

ok 1 number(s): "202725820"

Test #58:

score: 0
Accepted
time: 374ms
memory: 56488kb

input:

64 64 2080

output:

1

result:

ok 1 number(s): "1"

Test #59:

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

input:

1 1 0

output:

0

result:

ok 1 number(s): "0"

Test #60:

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

input:

1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #61:

score: 0
Accepted
time: 360ms
memory: 53780kb

input:

63 63 2016

output:

1

result:

ok 1 number(s): "1"