QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#691048 | #5586. Digits of Unity | ohiostatescarlet# | AC ✓ | 635ms | 146992kb | C++17 | 2.2kb | 2024-10-31 09:34:33 | 2024-10-31 09:34:33 |
Judging History
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;
}
} else {
if (j & i) {
bits++;
occEq = 0;
// occBel = occBel
} else {
// occEq = occEq
occBel = 2 * occBel;
}
}
j >>= 1;
}
occBel = 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: 3496kb
input:
3 4 14
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 10ms
memory: 5716kb
input:
2 1 100000
output:
910073387
result:
ok single line: '910073387'
Test #4:
score: 0
Accepted
time: 10ms
memory: 7276kb
input:
30 6 136665
output:
552360422
result:
ok single line: '552360422'
Test #5:
score: 0
Accepted
time: 5ms
memory: 4376kb
input:
178 6 51500
output:
788418998
result:
ok single line: '788418998'
Test #6:
score: 0
Accepted
time: 9ms
memory: 5736kb
input:
445 4 91471
output:
322733059
result:
ok single line: '322733059'
Test #7:
score: 0
Accepted
time: 30ms
memory: 11980kb
input:
23634 10 299334
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 33ms
memory: 11704kb
input:
242554 5 287650
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 3 7
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 1 7
output:
7
result:
ok single line: '7'
Test #12:
score: 0
Accepted
time: 613ms
memory: 146844kb
input:
500000 500000 5000000
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 627ms
memory: 146840kb
input:
250000 1 5000000
output:
578914111
result:
ok single line: '578914111'
Test #14:
score: 0
Accepted
time: 30ms
memory: 14276kb
input:
4096 6 449389
output:
129538870
result:
ok single line: '129538870'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
50 2 50
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 606ms
memory: 146844kb
input:
250000 65 5000000
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 635ms
memory: 146992kb
input:
1 1 5000000
output:
5000000
result:
ok single line: '5000000'
Test #18:
score: 0
Accepted
time: 605ms
memory: 146880kb
input:
2 17 5000000
output:
7104108
result:
ok single line: '7104108'