HDU 4651 Partition
Problem :
n的整数划分方案数。(n <= 100008)
Solution :
参考资料：
五角数 欧拉函数 五边形数定理 整数划分 一份详细的题解
欧拉函数的定义如下:
[phi(q) =prodlimits_{n=1}^{infty}(1-q^n)
]
五边形定理对欧拉函数展开如下:
[phi(q) = sum_{n = 0}^{n = infty}(-1)^nq^{frac{3n^2pm n}{2}}
]
其中 (frac{3n^2pm n}{2})为广义五边形数。
而欧拉函数的倒数为
[frac{1}{phi(q)} = prodlimits_{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^2pm 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;
}
}