QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#691048#5586. Digits of Unityohiostatescarlet#AC ✓635ms146992kbC++172.2kb2024-10-31 09:34:332024-10-31 09:34:33

Judging History

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

  • [2024-10-31 09:34:33]
  • 评测
  • 测评结果:AC
  • 用时:635ms
  • 内存:146992kb
  • [2024-10-31 09:34:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

ll MOD = 998244353;

ll* inv;
ll* fact;

ll nCr(ll n, ll r) {
    if (r > n || r < 0) return 0;
    return (n == r || r == 0) ? 1 : fact[n] * inv[n-r] % MOD * inv[r] % MOD;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int n, k, m;
    cin >> n >> k >> m;
    
    inv = new ll[m] - 1; inv[1] = 1;
    rep(i,2,m+1) inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    rep(i,2,m+1) inv[i] = (inv[i-1] * inv[i]) % MOD;
    fact = new ll[m] - 1; fact[1] = 1;
    rep(i,2,m+1) fact[i] = (fact[i-1] * i) % MOD;


    int totbit = 1;
    int mxbit = 1;
    while ((mxbit << 1) <= m) mxbit <<= 1, totbit++;
    int xorv = (1<<totbit)-1;
    vector<ll> dp(1 << totbit, 0);
    dp[xorv] = nCr(m, n);
    for (int i = 1; i <= m; i++) {
        int bits = 0;
        ll occEq = 1, occBel = 0;
        int j = mxbit;
        while (j) {
            if (j & m) {
                if (j & i) {
                    bits++;
                    // occEq = occEq
                    // occBel = occBel
                } else {
                    // occEq = occEq
                    occBel = 2 * occBel + occEq;
                }
            } else {
                if (j & i) {
                    bits++;
                    occEq = 0;
                    // occBel = occBel
                } else {
                    // occEq = occEq
                    occBel = 2 * occBel;
                }
            }
            j >>= 1;
        }
        occBel = occBel + occEq;
        if (occBel >= n) {
            ll options = nCr(occBel, n);
            dp[i^xorv] = options;
        }
    }
    rep(b,0,totbit) for(int i=(1<<totbit)-1; i >= 0; i--) if (i & 1 << b) dp[i] = (dp[i] - dp[i^(1 << b)] + MOD) % MOD;
    
    ll res = 0;
    rep(i,0,1<<totbit) if (__builtin_popcount(i) >= k) res = (dp[i^xorv] + res) % MOD;
    res = (res * fact[n]) % MOD;
    cout << res << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2 10

output:

6

result:

ok single line: '6'

Test #2:

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

input:

3 4 14

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 1 100000

output:

910073387

result:

ok single line: '910073387'

Test #4:

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

input:

30 6 136665

output:

552360422

result:

ok single line: '552360422'

Test #5:

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

input:

178 6 51500

output:

788418998

result:

ok single line: '788418998'

Test #6:

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

input:

445 4 91471

output:

322733059

result:

ok single line: '322733059'

Test #7:

score: 0
Accepted
time: 30ms
memory: 11980kb

input:

23634 10 299334

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 33ms
memory: 11704kb

input:

242554 5 287650

output:

0

result:

ok single line: '0'

Test #9:

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

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #10:

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

input:

1 3 7

output:

1

result:

ok single line: '1'

Test #11:

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

input:

1 1 7

output:

7

result:

ok single line: '7'

Test #12:

score: 0
Accepted
time: 613ms
memory: 146844kb

input:

500000 500000 5000000

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 627ms
memory: 146840kb

input:

250000 1 5000000

output:

578914111

result:

ok single line: '578914111'

Test #14:

score: 0
Accepted
time: 30ms
memory: 14276kb

input:

4096 6 449389

output:

129538870

result:

ok single line: '129538870'

Test #15:

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

input:

50 2 50

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 606ms
memory: 146844kb

input:

250000 65 5000000

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 635ms
memory: 146992kb

input:

1 1 5000000

output:

5000000

result:

ok single line: '5000000'

Test #18:

score: 0
Accepted
time: 605ms
memory: 146880kb

input:

2 17 5000000

output:

7104108

result:

ok single line: '7104108'