直接暴力跑背包的复杂度太高了,考虑优化。
发现值域很小,对值域从小到大跑背包。设 \(f_i\) 为用奇数个数凑出和为 \(i\) 的方案数,相对地 \(g_i\) 是用偶数个数。设当前枚举到的值为 \(x\),数量为 \(c_x\),那么我们要做的就是:
- \(f_i \times \binom{c_x}{d} \to f_{i + dx}, d \mid 2\);
- \(f_i \times \binom{c_x}{d} \to g_{i + dx}, d \nmid 2\);
- \(g_i \times \binom{c_x}{d} \to f_{i + dx}, d \nmid 2\);
- \(g_i \times \binom{c_x}{d} \to g_{i + dx}, d \mid 2\)。
至此可以观察出卷积形式,NTT 优化。
每次枚举 \(x\),实际上要做 \(4\) 次卷积,\(12\) 次 NTT。直接跑是 \(O(120 m \log m)\) 的,还是过不去。考虑做一些上界的优化,\(f_i, g_i\) 的上界设置为 \(\sum\limits_{j=1}^i j \times c_j\),就可以通过了。
code
// Problem: Ex - Odd Sum
// Contest: AtCoder - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)
// URL: https://atcoder.jp/contests/abc267/tasks/abc267_h
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2200100;
const ll mod = 998244353;
const ll G = 3;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, a[15], fac[maxn], ifac[maxn], f[maxn], g[maxn], r[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
typedef vector<ll> poly;
inline poly NTT(poly a, int op) {
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
if (i < r[i]) {
swap(a[i], a[r[i]]);
}
}
for (int k = 1; k < n; k <<= 1) {
ll wn = qpow(op == 1 ? G : qpow(G, mod - 2), (mod - 1) / (k << 1));
for (int i = 0; i < n; i += (k << 1)) {
ll w = 1;
for (int j = 0; j < k; ++j, w = w * wn % mod) {
ll x = a[i + j], y = w * a[i + j + k] % mod;
a[i + j] = (x + y) % mod;
a[i + j + k] = (x - y + mod) % mod;
}
}
}
return a;
}
inline poly operator * (poly a, poly b) {
a = NTT(a, 1);
b = NTT(b, 1);
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
a[i] = a[i] * b[i] % mod;
}
a = NTT(a, -1);
ll inv = qpow(n, mod - 2);
for (int i = 0; i < n; ++i) {
a[i] = a[i] * inv % mod;
}
return a;
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
++a[x];
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
f[0] = 1;
ll s = 0;
for (int x = 1; x <= 10; ++x) {
int k = 0;
while ((1 << k) <= min(s, m) + a[x] * x) {
++k;
}
for (int i = 1; i < (1 << k); ++i) {
r[i] = (r[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
poly A(1 << k), B(1 << k);
for (int i = 0; i <= min(s, m); ++i) {
A[i] = f[i];
}
for (int i = 0; i <= a[x] * x; ++i) {
B[i] = ((i % x || (i / x) % 2) ? 0 : C(a[x], i / x));
}
poly r1 = A * B;
A = poly(1 << k);
B = poly(1 << k);
for (int i = 0; i <= min(s, m); ++i) {
A[i] = g[i];
}
for (int i = 0; i <= a[x] * x; ++i) {
B[i] = ((i % x || (i / x) % 2 == 0) ? 0 : C(a[x], i / x));
}
poly r2 = A * B;
A = poly(1 << k);
B = poly(1 << k);
for (int i = 0; i <= min(s, m); ++i) {
A[i] = f[i];
}
for (int i = 0; i <= a[x] * x; ++i) {
B[i] = ((i % x || (i / x) % 2 == 0) ? 0 : C(a[x], i / x));
}
poly r3 = A * B;
A = poly(1 << k);
B = poly(1 << k);
for (int i = 0; i <= min(s, m); ++i) {
A[i] = g[i];
}
for (int i = 0; i <= a[x] * x; ++i) {
B[i] = ((i % x || (i / x) % 2) ? 0 : C(a[x], i / x));
}
poly r4 = A * B;
s += a[x] * x;
for (int i = 0; i <= min(s, m); ++i) {
f[i] = (r1[i] + r2[i]) % mod;
g[i] = (r3[i] + r4[i]) % mod;
}
}
printf("%lld\n", g[m]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest 267 Oddbeginner atcoder contest 267 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310