五边形数$p_i$定义为：$\frac{i(3i - 1)}{2}$。
一个定理：$\prod_{i=1}^{\infty} (1 - x^i) = \sum_{i=-\infty}^{\infty} (-1)^i x^{p_i}$。
证明自行看维基。
接下来看一道题：
题目链接
题意：对于$1 \leqslant i \leqslant n$，求$i$的整数拆分方案数。$1 \leqslant n \leqslant 10^5$。
显然答案的生成函数为$\prod_{i=1}^{\infty} \frac{1}{1 - x^i}$。然后我们就可以先ln再加起来再exp回去了。
那么我们就是要对$\prod_{i=1}^{\infty} (1 - x^i)$求逆。根据上面的定理，这个多项式在次数$\leqslant n$的时候非$0$的项数是$O(\sqrt{n})$级别的，那么我们就可以暴力求逆了，复杂度为$O(n\sqrt{n})$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 100000, mod = 998244353;
int n, f[maxn + 10];
inline int dec(int x, int y) {
x -= y; return x < 0 ? x + mod : x;
}
inline int mul(int x, int y) {
return 1ll * x * y % mod;
}
int main() {
scanf("%d", &n); f[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = -300; j <= 300; ++j) {
int v = j * (3 * j - 1) / 2;
if (v <= i && v) f[i] = dec(f[i], mul(f[i - v], j & 1 ? mod - 1 : 1));
}
printf("%d\n", f[i]);
}
}
|