QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#50175#4807. Melborp Lacissalcsealnot123#WA 379ms54564kbC++1.5kb2022-09-25 02:15:532022-09-25 02:15:56

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:15:56]
  • 评测
  • 测评结果:WA
  • 用时:379ms
  • 内存:54564kb
  • [2022-09-25 02:15:53]
  • 提交

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: 7920kb

input:

2 5 1

output:

12

result:

ok 1 number(s): "12"

Test #2:

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

input:

7 10 15

output:

2016

result:

ok 1 number(s): "2016"

Test #3:

score: 0
Accepted
time: 89ms
memory: 26560kb

input:

46 50 171

output:

645560469

result:

ok 1 number(s): "645560469"

Test #4:

score: 0
Accepted
time: 379ms
memory: 54492kb

input:

64 64 0

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 377ms
memory: 54564kb

input:

64 64 1

output:

326126263

result:

ok 1 number(s): "326126263"

Test #6:

score: 0
Accepted
time: 351ms
memory: 53408kb

input:

63 64 0

output:

4476118

result:

ok 1 number(s): "4476118"

Test #7:

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

input:

11 45 14

output:

963276342

result:

ok 1 number(s): "963276342"

Test #8:

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

input:

35 20 565

output:

0

result:

ok 1 number(s): "0"

Test #9:

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

input:

3 64 5

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 27ms
memory: 18848kb

input:

35 45 153

output:

181934997

result:

ok 1 number(s): "181934997"

Test #11:

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

input:

3 25 5

output:

0

result:

ok 1 number(s): "0"

Test #12:

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

input:

35 5 373

output:

740122840

result:

ok 1 number(s): "740122840"

Test #13:

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

input:

3 50 5

output:

0

result:

ok 1 number(s): "0"

Test #14:

score: 0
Accepted
time: 14ms
memory: 15536kb

input:

35 30 592

output:

0

result:

ok 1 number(s): "0"

Test #15:

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

input:

3 11 1

output:

540

result:

ok 1 number(s): "540"

Test #16:

score: 0
Accepted
time: 39ms
memory: 21116kb

input:

35 55 352

output:

656633208

result:

ok 1 number(s): "656633208"

Test #17:

score: 0
Accepted
time: 109ms
memory: 26820kb

input:

54 38 356

output:

215089708

result:

ok 1 number(s): "215089708"

Test #18:

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

input:

22 19 189

output:

0

result:

ok 1 number(s): "0"

Test #19:

score: 0
Accepted
time: 197ms
memory: 39936kb

input:

54 63 401

output:

987604839

result:

ok 1 number(s): "987604839"

Test #20:

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

input:

22 43 171

output:

827743481

result:

ok 1 number(s): "827743481"

Test #21:

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

input:

54 24 446

output:

551546514

result:

ok 1 number(s): "551546514"

Test #22:

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

input:

22 4 152

output:

0

result:

ok 1 number(s): "0"

Test #23:

score: 0
Accepted
time: 153ms
memory: 32064kb

input:

54 48 1306

output:

0

result:

ok 1 number(s): "0"

Test #24:

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

input:

22 29 7

output:

374430631

result:

ok 1 number(s): "374430631"

Test #25:

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

input:

54 9 1351

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

22 54 5

output:

267958047

result:

ok 1 number(s): "267958047"

Test #27:

score: 0
Accepted
time: 187ms
memory: 29832kb

input:

64 32 1315

output:

494251101

result:

ok 1 number(s): "494251101"

Test #28:

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

input:

33 12 332

output:

765350074

result:

ok 1 number(s): "765350074"

Test #29:

score: -100
Wrong Answer
time: 0ms
memory: 10396kb

input:

1 57 1

output:

0

result:

wrong answer 1st numbers differ - expected: '1', found: '0'