QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333521 | #5586. Digits of Unity | joelgun14# | AC ✓ | 325ms | 75080kb | C++14 | 2.2kb | 2024-02-20 04:58:21 | 2024-02-20 04:58:21 |
Judging History
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'