QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#691030#5586. Digits of Unityohiostatescarlet#WA 40ms12080kbC++172.2kb2024-10-31 09:29:162024-10-31 09:29:36

Judging History

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

  • [2024-10-31 09:29:36]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:12080kb
  • [2024-10-31 09:29:16]
  • 提交

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) % MOD;
                }
            } else {
                if (j & i) {
                    bits++;
                    occEq = 0;
                    // occBel = occBel
                } else {
                    // occEq = occEq
                    occBel = (2 * occBel) % MOD;
                }
            }
            j >>= 1;
        }
        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: 3544kb

input:

3 4 14

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 1 100000

output:

910073387

result:

ok single line: '910073387'

Test #4:

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

input:

30 6 136665

output:

552360422

result:

ok single line: '552360422'

Test #5:

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

input:

178 6 51500

output:

788418998

result:

ok single line: '788418998'

Test #6:

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

input:

445 4 91471

output:

322733059

result:

ok single line: '322733059'

Test #7:

score: 0
Accepted
time: 36ms
memory: 12080kb

input:

23634 10 299334

output:

0

result:

ok single line: '0'

Test #8:

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

input:

242554 5 287650

output:

0

result:

ok single line: '0'

Test #9:

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

input:

1 1 1

output:

0

result:

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