QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#127518 | #5586. Digits of Unity | batrr# | AC ✓ | 345ms | 134688kb | C++17 | 2.0kb | 2023-07-19 19:17:05 | 2023-07-19 19:17:06 |
Judging History
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'