QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#127518#5586. Digits of Unitybatrr#AC ✓345ms134688kbC++172.0kb2023-07-19 19:17:052023-07-19 19:17:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 19:17:06]
  • 评测
  • 测评结果:AC
  • 用时:345ms
  • 内存:134688kb
  • [2023-07-19 19:17:05]
  • 提交

answer

#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, K = 23, inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}


int n, k, m, ans;
int a[1 << K];

int f[1 << K], rf[1 << K], inv[1 << K];

int C(int n, int k) {
    return (0 <= k && k <= n) ? mult(f[n], mult(rf[k], rf[n - k])) : 0;
}

void solve() {
    f[0] = rf[0] = f[1] = rf[1] = inv[1] = 1;
    for (int i = 2; i < (1 << K); i++) {
        f[i] = mult(i, f[i - 1]);
        inv[i] = mult(inv[mod % i], sub(0, mod / i));
        rf[i] = mult(rf[i - 1], inv[i]);
    }

    cin >> n >> k >> m;
    for (int i = 1; i <= m; i++)
        a[i] = 1;
    for (int j = 0; j < K; j++)
        for (int i = 0; i < (1 << K); i++)
            if ((i >> j) & 1)
                a[i ^ (1 << j)] = sum(a[i ^ (1 << j)], a[i]);
    for (int i = 0; i < (1 << K); i++)
        a[i] = C(a[i], n);
    for (int j = 0; j < K; j++)
        for (int i = 0; i < (1 << K); i++)
            if ((i >> j) & 1)
                a[i ^ (1 << j)] = sub(a[i ^ (1 << j)], a[i]);
    for (int i = 0; i < (1 << K); i++)
        if (__builtin_popcount(i) >= k)
            ans = sum(ans, a[i]);
    ans = mult(ans, f[n]);
    cout << ans << "\n";
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 314ms
memory: 134628kb

input:

2 2 10

output:

6

result:

ok single line: '6'

Test #2:

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

input:

3 4 14

output:

0

result:

ok single line: '0'

Test #3:

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

input:

2 1 100000

output:

910073387

result:

ok single line: '910073387'

Test #4:

score: 0
Accepted
time: 299ms
memory: 134440kb

input:

30 6 136665

output:

552360422

result:

ok single line: '552360422'

Test #5:

score: 0
Accepted
time: 310ms
memory: 134472kb

input:

178 6 51500

output:

788418998

result:

ok single line: '788418998'

Test #6:

score: 0
Accepted
time: 322ms
memory: 134476kb

input:

445 4 91471

output:

322733059

result:

ok single line: '322733059'

Test #7:

score: 0
Accepted
time: 307ms
memory: 134532kb

input:

23634 10 299334

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 309ms
memory: 134508kb

input:

242554 5 287650

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 299ms
memory: 134480kb

input:

1 1 1

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 298ms
memory: 134436kb

input:

1 3 7

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 297ms
memory: 134432kb

input:

1 1 7

output:

7

result:

ok single line: '7'

Test #12:

score: 0
Accepted
time: 282ms
memory: 134472kb

input:

500000 500000 5000000

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 292ms
memory: 134540kb

input:

250000 1 5000000

output:

578914111

result:

ok single line: '578914111'

Test #14:

score: 0
Accepted
time: 299ms
memory: 134524kb

input:

4096 6 449389

output:

129538870

result:

ok single line: '129538870'

Test #15:

score: 0
Accepted
time: 301ms
memory: 134688kb

input:

50 2 50

output:

0

result:

ok single line: '0'

Test #16:

score: 0
Accepted
time: 304ms
memory: 134592kb

input:

250000 65 5000000

output:

0

result:

ok single line: '0'

Test #17:

score: 0
Accepted
time: 345ms
memory: 134628kb

input:

1 1 5000000

output:

5000000

result:

ok single line: '5000000'

Test #18:

score: 0
Accepted
time: 305ms
memory: 134504kb

input:

2 17 5000000

output:

7104108

result:

ok single line: '7104108'