QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#50716#4807. Melborp LacissalcalittlestoryAC ✓11ms3752kbC++2.8kb2022-09-28 20:15:412022-09-28 20:15:44

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-28 20:15:44]
  • 评测
  • 测评结果:AC
  • 用时:11ms
  • 内存:3752kb
  • [2022-09-28 20:15:41]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long long ll;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a, ll b, ll mod) {ll res=1;a%=mod;
assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;
a=a*a%mod;};return res;}
ll gcd(ll a, ll b) {return b?gcd(b, a%b):a;}
template<class T> 
void chkmin(T&x,T y){x=min(x,y);}
template<class T> 
void chkmax(T&x,T y){x=max(x,y);}
template<class T> 
void add(T&x,T y){x+=y;if(x>=mod)x-=mod;}
template<class T> 
void sub(T&x,T y){x-=y;if(x<0)x+=mod;}
// head 
const int N = 110;
int n, k, t, cnt;
int a[N];
ll f[N], ans, invf[N];

ll c(int n, int m) {
    //cout << n << ' ' << m << '\n';
    if (n < m) return 0;
    return f[n] * invf[m] % mod * invf[n - m] % mod;
}

void dfs(int x, int cur, int last, int res, int tot) {
    //cout << cur << '\n';
    if ((x - cur) * last < res) return;
    if (tot > t) return ;
    if (tot + res * (res - 1) / 2 < t) return ;

    if (cur == x) {
        if (res || tot != t) return;
        /*cout << cnt << ' ';
        for (int i = 0; i < x; i++) cout << a[i] << ' ';
        cout << '\n';*/
        ll p = f[x];
        VI b;
        if (cnt) b.pb(cnt);
        for (int i = 0; i < x; i++)
            if (a[i]) b.pb(a[i]);
        for (int i = 0, j; i < x; i = j + 1) {
            j = i;
            while (j + 1 < x && a[j + 1] == a[j]) ++j;
            p = p * powmod(f[j - i + 1], mod - 2, mod) % mod;
        }    

        //cout << p << '\n';
        int r = n;
        for (int i : b) {
            p = c(r, i) * p % mod;
            r -= i;
        }
        //cout << p << '\n';            
        add(ans, p);
        return ;
    }

    for (int i = min(res, last); i >= 0; i--) {
        a[cur] = i;
        dfs(x, cur + 1, i, res - i, tot + i * (i - 1) / 2);
    }
}

void solve() {
    // to solve a single test case 
    f[0] = 1;
    cin >> n >> k >> t;
    for (int i = 1; i <= 64; i++) {
        f[i] = f[i - 1] * i % mod;
        invf[i] = powmod(f[i], mod - 2, mod);
    }

    invf[0] = 1;

    for (cnt = 0; cnt <= n; cnt++) {
        //cout << cnt << '\n';
        dfs(k - 1, 0, n - cnt, n - cnt, cnt * (cnt + 1) / 2);
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int tt;
    //cin >> tt;
    tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3644kb

input:

2 5 1

output:

12

result:

ok 1 number(s): "12"

Test #2:

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

input:

7 10 15

output:

2016

result:

ok 1 number(s): "2016"

Test #3:

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

input:

46 50 171

output:

645560469

result:

ok 1 number(s): "645560469"

Test #4:

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

input:

64 64 0

output:

0

result:

ok 1 number(s): "0"

Test #5:

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

input:

64 64 1

output:

326126263

result:

ok 1 number(s): "326126263"

Test #6:

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

input:

63 64 0

output:

4476118

result:

ok 1 number(s): "4476118"

Test #7:

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

input:

11 45 14

output:

963276342

result:

ok 1 number(s): "963276342"

Test #8:

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

input:

35 20 565

output:

0

result:

ok 1 number(s): "0"

Test #9:

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

input:

3 64 5

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

35 45 153

output:

181934997

result:

ok 1 number(s): "181934997"

Test #11:

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

input:

3 25 5

output:

0

result:

ok 1 number(s): "0"

Test #12:

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

input:

35 5 373

output:

740122840

result:

ok 1 number(s): "740122840"

Test #13:

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

input:

3 50 5

output:

0

result:

ok 1 number(s): "0"

Test #14:

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

input:

35 30 592

output:

0

result:

ok 1 number(s): "0"

Test #15:

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

input:

3 11 1

output:

540

result:

ok 1 number(s): "540"

Test #16:

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

input:

35 55 352

output:

656633208

result:

ok 1 number(s): "656633208"

Test #17:

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

input:

54 38 356

output:

215089708

result:

ok 1 number(s): "215089708"

Test #18:

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

input:

22 19 189

output:

0

result:

ok 1 number(s): "0"

Test #19:

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

input:

54 63 401

output:

987604839

result:

ok 1 number(s): "987604839"

Test #20:

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

input:

22 43 171

output:

827743481

result:

ok 1 number(s): "827743481"

Test #21:

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

input:

54 24 446

output:

551546514

result:

ok 1 number(s): "551546514"

Test #22:

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

input:

22 4 152

output:

0

result:

ok 1 number(s): "0"

Test #23:

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

input:

54 48 1306

output:

0

result:

ok 1 number(s): "0"

Test #24:

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

input:

22 29 7

output:

374430631

result:

ok 1 number(s): "374430631"

Test #25:

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

input:

54 9 1351

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

22 54 5

output:

267958047

result:

ok 1 number(s): "267958047"

Test #27:

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

input:

64 32 1315

output:

494251101

result:

ok 1 number(s): "494251101"

Test #28:

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

input:

33 12 332

output:

765350074

result:

ok 1 number(s): "765350074"

Test #29:

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

input:

1 57 1

output:

1

result:

ok 1 number(s): "1"

Test #30:

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

input:

33 37 363

output:

0

result:

ok 1 number(s): "0"

Test #31:

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

input:

1 17 0

output:

16

result:

ok 1 number(s): "16"

Test #32:

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

input:

33 62 148

output:

871819399

result:

ok 1 number(s): "871819399"

Test #33:

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

input:

1 42 0

output:

41

result:

ok 1 number(s): "41"

Test #34:

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

input:

33 23 179

output:

23699248

result:

ok 1 number(s): "23699248"

Test #35:

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

input:

1 3 1

output:

1

result:

ok 1 number(s): "1"

Test #36:

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

input:

33 47 211

output:

267909794

result:

ok 1 number(s): "267909794"

Test #37:

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

input:

11 26 32

output:

0

result:

ok 1 number(s): "0"

Test #38:

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

input:

43 6 579

output:

280289125

result:

ok 1 number(s): "280289125"

Test #39:

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

input:

11 50 5

output:

865381083

result:

ok 1 number(s): "865381083"

Test #40:

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

input:

43 31 750

output:

0

result:

ok 1 number(s): "0"

Test #41:

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

input:

11 11 12

output:

753565341

result:

ok 1 number(s): "753565341"

Test #42:

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

input:

43 56 290

output:

575236094

result:

ok 1 number(s): "575236094"

Test #43:

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

input:

11 36 52

output:

0

result:

ok 1 number(s): "0"

Test #44:

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

input:

44 16 0

output:

0

result:

ok 1 number(s): "0"

Test #45:

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

input:

12 61 31

output:

682427534

result:

ok 1 number(s): "682427534"

Test #46:

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

input:

44 41 365

output:

759457870

result:

ok 1 number(s): "759457870"

Test #47:

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

input:

22 19 70

output:

247296498

result:

ok 1 number(s): "247296498"

Test #48:

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

input:

54 64 444

output:

418216086

result:

ok 1 number(s): "418216086"

Test #49:

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

input:

22 44 52

output:

779702126

result:

ok 1 number(s): "779702126"

Test #50:

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

input:

54 25 1303

output:

0

result:

ok 1 number(s): "0"

Test #51:

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

input:

22 5 49

output:

219556981

result:

ok 1 number(s): "219556981"

Test #52:

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

input:

54 49 1269

output:

0

result:

ok 1 number(s): "0"

Test #53:

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

input:

22 30 14

output:

719775605

result:

ok 1 number(s): "719775605"

Test #54:

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

input:

54 10 1314

output:

0

result:

ok 1 number(s): "0"

Test #55:

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

input:

22 54 12

output:

325137058

result:

ok 1 number(s): "325137058"

Test #56:

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

input:

54 35 1359

output:

0

result:

ok 1 number(s): "0"

Test #57:

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

input:

33 13 335

output:

202725820

result:

ok 1 number(s): "202725820"

Test #58:

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

input:

64 64 2080

output:

1

result:

ok 1 number(s): "1"

Test #59:

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

input:

1 1 0

output:

0

result:

ok 1 number(s): "0"

Test #60:

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

input:

1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #61:

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

input:

63 63 2016

output:

1

result:

ok 1 number(s): "1"