这道题最简单的方法实际上是多项式。
第一种物品的生成函数为 $\mathcal{A(x)} = 1 + x ^ {10} +x ^ {20} \cdots$
第二种物品同理,为 $\mathcal{B(x)} = 1 +x ^ {20} +x ^ {40} \cdots$
第三种物品为 $\mathcal{C(x)} = 1 + x ^ {50} +x ^ {100} + \cdots$
第四种为 $\mathcal{D(x)} = 1 +x ^ {100} + x ^ {200} \cdots$
将四个函数卷积起来即可。这个过程可以用 $\texttt{FFT}$ 实现。复杂度 $n \log n$。
因此这道题还可以扩展到更加复杂的情况。例如,假设我们现在有 $m$ 中货币,使用分治 $\texttt{FFT}$ 即可做到 $O(n \log n \log m)$ 的优秀复杂度。这可以吊打 $O(nm)$ 的背包。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
using namespace std;
const int N = 1000010;
int a[N], b[N], c[N], d[N], n;
namespace Poly {
const int g = 3;
const int p = 998244353;
int invg, invn; int *rev;
int Mod(int a) { return (a % p + p) % p; }
int qpow(int a, int b = p - 2, int s = 1) {
for (; b; b >>= 1, a = 1ll * a * a % p)
if (b & 1) s = 1ll * s * a % p; return s;
} int inv(int x) { return qpow(x); }
void NTT(int *a, int n, int op) {
rop(i, 0, n) if (i < rev[i]) swap(a[i], a[rev[i]]);
for (int mid = 1; (mid << 1) <= n; mid = mid << 1) {
int gn = qpow((op == 1) ? g : invg, (p - 1) / (mid << 1));
for (int i = 0, gk = 1; i < n; i += (mid << 1), gk = 1) {
for (int j = 0; j < mid; j ++ , gk = 1ll * gk * gn % p) {
int x = a[i + j], y = 1ll * a[i + j + mid] * gk % p;
a[i + j] = Mod(x + y), a[i + j + mid] = Mod(x - y);
}
}
}
}
void NTT(int *a, int n, int *b, int m) {
int B = ((n + m) << 2) + 1; rev = new int [B]();
m = n + m, n = 1; int bit = 0;
while (n <= m) bit ++ , n <<= 1; bit -- ;
invg = inv(g); invn = inv(n);
rop(i, 0, n) rev[i] = (rev[i >> 1] >> 1) | (i & 1) << bit;
NTT(a, n, 1), NTT(b, n, 1);
rop(i, 0, n) a[i] = 1ll * a[i] * b[i] % p; NTT(a, n, -1);
rep(i, 0, m) a[i] = 1ll * a[i] * invn % p; free(rev); rev = NULL;
}
}
int main() {
scanf("%d", &n);
rep(i, 0, n) if (i % 10 == 0) a[i] = 1;
rep(i, 0, n) if (i % 20 == 0) b[i] = 1;
rep(i, 0, n) if (i % 50 == 0) c[i] = 1;
rep(i, 0, n) if (i % 100 == 0) d[i] = 1;
Poly::NTT(a, n, b, n);
Poly::NTT(a, n, c, n);
Poly::NTT(a, n, d, n);
printf("%d\n", a[n]);
}