HDU 4651 Partition
Problem :
n的整数划分方案数。(n <= 100008)
Solution :
参考资料：
五角数 欧拉函数 五边形数定理 整数划分 一份详细的题解
欧拉函数的定义如下:
\[\phi(q) =\prod\limits_{n=1}^{\infty}(1-q^n)
\]
\]
五边形定理对欧拉函数展开如下:
\[\phi(q) = \sum_{n = 0}^{n = \infty}(-1)^nq^{\frac{3n^2\pm n}{2}}
\]
\]
其中 \(\frac{3n^2\pm n}{2}\)为广义五边形数。
而欧拉函数的倒数为
\[\frac{1}{\phi(q)} = \prod\limits_{n = 1}^{\infty} \frac{1}{1-q^k}
\]
\]
\[\frac{1}{\phi(q)} = (1 + q + q ^2 + \cdots)(1 + q ^ 2 + q ^ 4 + \cdots)(1 + q ^ 3 + q ^ 6 + \cdots)'\cdots
\]
\]
\[\frac{1}{\phi(q)}= \sum_{n =0}^{\infty}P(q) q^n
\]
\]
其中P(q)即为q的整数划分方案数，可以从展开式的意义考虑，对于第一个括号表示1取几个，第二个括号表示2取几个，以此类推。
将上下两个式子相乘即得到
\[\sum_{n =0}^{\infty}P(q) q^n * \sum_{n = 0}^{n = \infty}(-1)^nq^{\frac{3n^2\pm n}{2}} = 1
\]
\]
\[(1 + P(1) * q + P(2) * q^2 + P(3) * q ^ 2 + \cdots)(1 - q - q ^ 2 + q ^ 5 + \cdots) = 1
\]
\]
展开可得到
\[P(n) = \sum_{i = 1} (-1)^{i -1} P(n - \frac{3*i^2 \pm i}{2})
\]
\]
其中要保证括号内的数大于等于0.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
using namespace std;
const int N = 1e5 + 8;
const int mo = 1e9 + 7;
int dp[N];
int main()
{
cin.sync_with_stdio(0);
int n = 1e5;
dp[0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = 1, tmp = 1; i >= (3 * j * j - j) / 2; ++j, tmp *= -1)
{
int x = (3 * j * j - j) / 2;
int y = (3 * j * j + j) / 2;
dp[i] = ((dp[i] + tmp * dp[i - x]) % mo + mo) % mo;
if (i >= y) dp[i] = ((dp[i] + tmp * dp[i - y]) % mo + mo) % mo;
}
}
int T; cin >> T;
while (T--)
{
int n; cin >> n;
cout << dp[n] << endl;
}
}