QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#67526 | #2590. 唱、跳、rap和篮球 | alpha1022 | 100 ✓ | 7ms | 1768kb | C++23 | 4.0kb | 2022-12-10 16:59:31 | 2022-12-10 16:59:35 |
Judging History
answer
#include <cmath>
#include <cstdio>
#include <algorithm>
using ll = long long;
using namespace std;
const int mod = 998244353;
inline int norm(int x) {
return x >= mod ? x - mod : x;
}
inline int reduce(int x) {
return x < 0 ? x + mod : x;
}
inline int neg(int x) {
return x ? mod - x : 0;
}
inline void add(int &x, int y) {
if ((x += y - mod) < 0)
x += mod;
}
inline void sub(int &x, int y) {
if ((x -= y) < 0)
x += mod;
}
inline void fam(int &x, int y, int z) {
x = (x + (ll)y * z) % mod;
}
inline int qpow(int a, int b) {
int ret = 1;
for (; b; b >>= 1)
(b & 1) && (ret = (ll)ret * a % mod),
a = (ll)a * a % mod;
return ret;
}
const int N = 1e3;
const int K = 4;
const int MX = 2e3;
const int inf = 0x3f3f3f3f;
int n, a[K], mx, minAi, sumAi, lim, S;
int subsetSum[1 << K];
inline int lowbit(int x) {
return x & -x;
}
int fac[MX + 5], ifac[MX + 5], inv[MX + 5];
int f[1 << K][N + 5], g[1 << K][N + 5];
int ans;
int main() {
scanf("%d", &n);
minAi = inf;
for (int i = 0; i < K; ++i)
scanf("%d", a + i), subsetSum[1 << i] = a[i], minAi = min(minAi, a[i]);
for (int s = 0; s < (1 << K); ++s)
subsetSum[s] = subsetSum[s ^ lowbit(s)] + subsetSum[lowbit(s)];
sumAi = subsetSum[(1 << K) - 1];
mx = max(n, subsetSum[(1 << K) - 1]);
fac[0] = 1;
for (int i = 1; i <= mx; ++i)
fac[i] = (ll)fac[i - 1] * i % mod;
ifac[mx] = qpow(fac[mx], mod - 2);
for (int i = mx; i; --i)
ifac[i - 1] = (ll)ifac[i] * i % mod;
for (int i = 1; i <= mx; ++i)
inv[i] = (ll)ifac[i] * fac[i - 1] % mod;
lim = min(minAi, n / 4), S = sqrt(lim);
for (int l = 0; l <= lim; l += S) {
int low[1 << K];
for (int s = 0; s < (1 << K); ++s)
f[s][0] = 1;
for (int k = 1; k <= sumAi - 4 * l && k <= n - 4 * l; ++k)
for (int s = 0; s < (1 << K); ++s) {
f[s][k] = (ll)__builtin_popcount(s) * f[s][k - 1] % mod;
for (int i = 0; i < K; ++i)
if (s & (1 << i) && a[i] - l < k)
fam(f[s][k], f[s ^ (1 << i)][k - 1 - (a[i] - l)], neg(ifac[a[i] - l]));
f[s][k] = (ll)f[s][k] * inv[k] % mod;
}
if (l & 1)
ans = (ans - (ll)fac[n - 3 * l] * ifac[l] % mod * f[(1 << K) - 1][n - 4 * l] % mod + mod) % mod;
else
ans = (ans + (ll)fac[n - 3 * l] * ifac[l] % mod * f[(1 << K) - 1][n - 4 * l]) % mod;
for (int r = l + 1; r < l + S && r <= lim; ++r) {
int m = n - 4 * r, sum = 0;
g[0][0] = 1;
for (int i = 0; i < K; ++i)
g[1 << i][a[i] - r + 1] = ifac[a[i] - r + 1];
for (int s = 0; s < (1 << K); ++s) {
low[s] = subsetSum[s] - __builtin_popcount(s) * (r - 1),
g[s][low[s]] = (ll)g[s ^ lowbit(s)][low[s ^ lowbit(s)]] * g[lowbit(s)][low[lowbit(s)]] % mod;
if (low[s] <= m && g[s][low[s]]) {
if (__builtin_popcount(s) & 1)
fam(sum, neg(g[s][low[s]]), f[((1 << K) - 1) ^ s][m - low[s]]);
else
fam(sum, g[s][low[s]], f[((1 << K) - 1) ^ s][m - low[s]]);
}
}
for (int k = 1; k <= sumAi - 4 * l && k <= m; ++k)
for (int s = 0; s < (1 << K); ++s)
if (k < low[s])
g[s][k] = 0;
else if (k > low[s]) {
g[s][k] = (ll)__builtin_popcount(s) * g[s][k - 1] % mod;
for (int i = 0; i < K; ++i)
if (s & (1 << i) && a[i] - r < k) {
fam(g[s][k], g[s ^ (1 << i)][k - 1 - (a[i] - r)], ifac[a[i] - r]);
if (a[i] - l < k)
fam(g[s][k], g[s ^ (1 << i)][k - 1 - (a[i] - l)], neg(ifac[a[i] - l]));
}
if (!g[s][k])
continue;
g[s][k] = (ll)g[s][k] * inv[k] % mod;
if (__builtin_popcount(s) & 1)
fam(sum, neg(g[s][k]), f[((1 << K) - 1) ^ s][m - k]);
else
fam(sum, g[s][k], f[((1 << K) - 1) ^ s][m - k]);
}
int coe = (ll)fac[m + r] * ifac[r] % mod;
if (r & 1)
coe = neg(coe);
fam(ans, coe, sum);
}
}
printf("%d\n", ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 10
Accepted
time: 1ms
memory: 1596kb
input:
7 2 6 8 7
output:
12176
result:
ok single line: '12176'
Test #2:
score: 10
Accepted
time: 1ms
memory: 1660kb
input:
8 8 8 8 8
output:
64257
result:
ok single line: '64257'
Test #3:
score: 10
Accepted
time: 1ms
memory: 1668kb
input:
13 2 9 7 10
output:
21225793
result:
ok single line: '21225793'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1672kb
input:
20 6 3 9 5
output:
516020500
result:
ok single line: '516020500'
Test #5:
score: 10
Accepted
time: 1ms
memory: 1680kb
input:
14 5 8 1 10
output:
19436472
result:
ok single line: '19436472'
Test #6:
score: 10
Accepted
time: 5ms
memory: 1668kb
input:
930 490 275 473 441
output:
686063454
result:
ok single line: '686063454'
Test #7:
score: 10
Accepted
time: 7ms
memory: 1736kb
input:
853 420 252 120 139
output:
570353775
result:
ok single line: '570353775'
Test #8:
score: 10
Accepted
time: 2ms
memory: 1768kb
input:
900 307 481 236 499
output:
28060009
result:
ok single line: '28060009'
Test #9:
score: 10
Accepted
time: 0ms
memory: 1672kb
input:
195 458 380 385 44
output:
946454887
result:
ok single line: '946454887'
Test #10:
score: 10
Accepted
time: 1ms
memory: 1764kb
input:
231 231 231 231 231
output:
793921530
result:
ok single line: '793921530'