QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333521#5586. Digits of Unityjoelgun14#AC ✓325ms75080kbC++142.2kb2024-02-20 04:58:212024-02-20 04:58:21

Judging History

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

  • [2024-02-20 04:58:21]
  • 评测
  • 测评结果:AC
  • 用时:325ms
  • 内存:75080kb
  • [2024-02-20 04:58:21]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
using namespace std;

template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}

const int N = 2e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 998244353;

void add(int &a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
}

int bpow(int x, int k) {
    int res = 1;
    for (; k; k >>= 1, x = (long long) x * x % mod)
        if (k & 1) 
            res = (long long) res * x % mod;
    return res;
}



int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);  
    int n,k,m;
    cin >> n >> k >> m;
    vector <int> fac(m + 1), inv(m + 1);
    fac[0] = 1;
    for (int i = 1; i <= m; i++) {
        fac[i] = (long long) fac[i - 1] * i % mod;
    }   
    inv[m] = bpow(fac[m], mod - 2);

    for (int i = m - 1; i >= 0; i--) {
        inv[i] = (long long) inv[i + 1] * (i + 1) % mod;
    }

    auto comb = [&](int k, int n) {
        if (k > n)
            return 0LL;
        return (long long) fac[n] * inv[k] % mod * inv[n - k] % mod;
    };

    vector <int> num(bit(23));
    for (int i = 1; i <= m; i++) 
        num[i] = 1;

    for (int i = 0; i < 23; i++)
    for (int mask = bit(23) - 1; mask >= 0; mask--) {
        if (!getbit(mask, i))
            add(num[mask], num[mask ^ bit(i)]);
    }

    // for (int i = 0; i <= m; i++) {
    //     cerr << i << " " << num[i] << "\n";
    // }


    for (int mask = 0; mask < bit(23); mask++) 
        num[mask] = comb(n, num[mask]); 

    for (int i = 0; i < 23; i++) 
    for (int mask = bit(23) - 1; mask >= 0; mask--) {
        if (!getbit(mask, i)) 
            add(num[mask], mod - num[mask ^ bit(i)]);
    }

    int ans = 0;
    for (int mask = 0; mask < bit(23); mask++) 
        if (__builtin_popcount(mask) >= k)
            add(ans, num[mask]); 

    cout << (long long) ans * fac[n] % mod << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 263ms
memory: 35892kb

input:

2 2 10

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 268ms
memory: 35892kb

input:

3 4 14

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 285ms
memory: 36608kb

input:

2 1 100000

output:

910073387

result:

ok single line: '910073387'

Test #4:

score: 0
Accepted
time: 271ms
memory: 37028kb

input:

30 6 136665

output:

552360422

result:

ok single line: '552360422'

Test #5:

score: 0
Accepted
time: 270ms
memory: 36496kb

input:

178 6 51500

output:

788418998

result:

ok single line: '788418998'

Test #6:

score: 0
Accepted
time: 267ms
memory: 36632kb

input:

445 4 91471

output:

322733059

result:

ok single line: '322733059'

Test #7:

score: 0
Accepted
time: 267ms
memory: 38180kb

input:

23634 10 299334

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 277ms
memory: 38348kb

input:

242554 5 287650

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 276ms
memory: 35804kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 267ms
memory: 35800kb

input:

1 3 7

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 269ms
memory: 35908kb

input:

1 1 7

output:

7

result:

ok single line: '7'

Test #12:

score: 0
Accepted
time: 314ms
memory: 75080kb

input:

500000 500000 5000000

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 324ms
memory: 75056kb

input:

250000 1 5000000

output:

578914111

result:

ok single line: '578914111'

Test #14:

score: 0
Accepted
time: 273ms
memory: 39620kb

input:

4096 6 449389

output:

129538870

result:

ok single line: '129538870'

Test #15:

score: 0
Accepted
time: 265ms
memory: 35836kb

input:

50 2 50

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 320ms
memory: 75044kb

input:

250000 65 5000000

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 319ms
memory: 74996kb

input:

1 1 5000000

output:

5000000

result:

ok single line: '5000000'

Test #18:

score: 0
Accepted
time: 325ms
memory: 75036kb

input:

2 17 5000000

output:

7104108

result:

ok single line: '7104108'