QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#641884 | #2590. 唱、跳、rap和篮球 | Elegia | 100 ✓ | 2ms | 3924kb | C++14 | 3.5kb | 2024-10-15 03:07:27 | 2024-10-15 03:07:28 |
Judging History
answer
#include <bits/stdc++.h>
#define popcnt __builtin_popcount
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int P = 998244353;
int norm(int x) { return x >= P ? (x - P) : x; }
void add(int &x, int y) { if ((x += y) >= P) x -= P; }
void sub(int &x, int y) { if ((x -= y) < 0) x += P; }
void exGcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return;
}
exGcd(b, a % b, y, x);
y -= a / b * x;
}
int inv(int a) {
int x, y;
exGcd(a, P, x, y);
return norm(x + P);
}
const int N = 1010, K = 4;
int l[K], r[K];
int f[1 << K][N], g[1 << K][N];
int fac[N], ifac[N], nv[N];
int main() {
#ifdef ELEGIA
freopen("test.in", "r", stdin);
int nol_cl = clock();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < K; ++i) cin >> r[i];
fac[0] = 1;
for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * (ull) i % P;
ifac[n] = inv(fac[n]);
for (int i = n; i; --i) ifac[i - 1] = ifac[i] * (ull) i % P;
for (int i = 1; i <= n; ++i) nv[i] = ifac[i] * (ull) fac[i - 1] % P;
int A = min(*min_element(r, r + K), n / K), B = sqrt(n);
memcpy(l, r, sizeof(l));
int ans = 0, U = (1 << K) - 1;
g[0][0] = 1;
for (int i = 0; i <= A; ++i) {
if (i % B == 0) {
memset(f, 0, sizeof(f));
f[0][0] = 1;
for (int s = 1; s != 1 << K; ++s) {
f[s][0] = 1;
int v = 1;
int t = popcnt(s);
for (int j = 1; j <= n - i * K; ++j) {
v = v * (ull) t % P;
for (int k = 0; k < K; ++k)
if (s >> k & 1 && r[k] < j)
v = (v + (P - ifac[r[k]]) * (ull) f[s ^ 1 << k][j - r[k] - 1]) % P;
v = v * (ull) nv[j] % P;
f[s][j] = v;
}
}
}
int w = f[U][n - i * K];
if (i % B) {
for (int s = 1; s != 1 << K; ++s) {
int L = 0, R = 0, v = 1;
for (int j = 0; j < K; ++j)
if ((s >> j) & 1) {
L += l[j] + 1;
R += r[j];
v = v * (ull) (P - ifac[l[j] + 1]) % P;
}
if (L > n - i * K) continue;
g[s][L] = v;
R = min(R, n - i * K);
int t = popcnt(s);
for (int j = L + 1; j <= R; ++j) {
v = v * (ull) t % P;
for (int k = 0; k < K; ++k)
if (s >> k & 1) {
if (l[k] < j) v = (v + (P - ifac[l[k]]) * (ull) g[s ^ 1 << k][j - l[k] - 1]) % P;
if (r[k] < j) v = (v + ifac[r[k]] * (ull) g[s ^ 1 << k][j - r[k] - 1]) % P;
}
v = v * (ull) nv[j] % P;
g[s][j] = v;
}
for (int j = L; j <= R; ++j)
w = (w + g[s][j] * (ull) f[U ^ s][n - i * K - j]) % P;
}
for (int s = 1; s != 1 << K; ++s) {
int L = 0, R = 0;
for (int j = 0; j < K; ++j)
if ((s >> j) & 1) {
L += l[j] + 1;
R += r[j];
}
if (L > n - i * K) continue;
memset(g[s] + L, 0, sizeof(int) * (min(R, n - i * K) - L + 1));
}
}
w = w * (ull) ifac[i] % P * fac[n - i * (K - 1)] % P;
if (i & 1) sub(ans, w);
else add(ans, w);
for (int j = 0; j < K; ++j) --l[j];
if ((i + 1) % B == 0) memcpy(r, l, sizeof(r));
}
cout << ans << '\n';
#ifdef ELEGIA
LOG("Time: %dms\n", int ((clock()
-nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 3700kb
input:
7 2 6 8 7
output:
12176
result:
ok single line: '12176'
Test #2:
score: 10
Accepted
time: 0ms
memory: 3924kb
input:
8 8 8 8 8
output:
64257
result:
ok single line: '64257'
Test #3:
score: 10
Accepted
time: 0ms
memory: 3648kb
input:
13 2 9 7 10
output:
21225793
result:
ok single line: '21225793'
Test #4:
score: 10
Accepted
time: 0ms
memory: 3668kb
input:
20 6 3 9 5
output:
516020500
result:
ok single line: '516020500'
Test #5:
score: 10
Accepted
time: 0ms
memory: 3860kb
input:
14 5 8 1 10
output:
19436472
result:
ok single line: '19436472'
Test #6:
score: 10
Accepted
time: 1ms
memory: 3736kb
input:
930 490 275 473 441
output:
686063454
result:
ok single line: '686063454'
Test #7:
score: 10
Accepted
time: 2ms
memory: 3828kb
input:
853 420 252 120 139
output:
570353775
result:
ok single line: '570353775'
Test #8:
score: 10
Accepted
time: 2ms
memory: 3692kb
input:
900 307 481 236 499
output:
28060009
result:
ok single line: '28060009'
Test #9:
score: 10
Accepted
time: 1ms
memory: 3580kb
input:
195 458 380 385 44
output:
946454887
result:
ok single line: '946454887'
Test #10:
score: 10
Accepted
time: 1ms
memory: 3632kb
input:
231 231 231 231 231
output:
793921530
result:
ok single line: '793921530'