QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#691030 | #5586. Digits of Unity | ohiostatescarlet# | WA | 40ms | 12080kb | C++17 | 2.2kb | 2024-10-31 09:29:16 | 2024-10-31 09:29:36 |
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) % MOD;
}
} else {
if (j & i) {
bits++;
occEq = 0;
// occBel = occBel
} else {
// occEq = occEq
occBel = (2 * occBel) % MOD;
}
}
j >>= 1;
}
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";
}
详细
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: 3544kb
input:
3 4 14
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 8ms
memory: 5688kb
input:
2 1 100000
output:
910073387
result:
ok single line: '910073387'
Test #4:
score: 0
Accepted
time: 16ms
memory: 7280kb
input:
30 6 136665
output:
552360422
result:
ok single line: '552360422'
Test #5:
score: 0
Accepted
time: 6ms
memory: 4644kb
input:
178 6 51500
output:
788418998
result:
ok single line: '788418998'
Test #6:
score: 0
Accepted
time: 12ms
memory: 5820kb
input:
445 4 91471
output:
322733059
result:
ok single line: '322733059'
Test #7:
score: 0
Accepted
time: 36ms
memory: 12080kb
input:
23634 10 299334
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 40ms
memory: 11772kb
input:
242554 5 287650
output:
0
result:
ok single line: '0'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3616kb
input:
1 1 1
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'