https://loj.ac/p/6268
by ForgotDream_CHN @ 2023-10-28 17:11:40
[这个是通项](https://oeis.org/A000041)
by ForgotDream_CHN @ 2023-10-28 17:15:46
我在一个外国论坛上找到了一个计算方法及详解和代码
原网址：
[Calculating integer partitions](https://math.stackexchange.com/questions/2675382/calculating-integer-partitions)
解析如下（机翻）
还有一个近似求解公式
原网址给出了python代码
```
def pentagonal_number(k):
return int(k*(3*k-1) / 2)
def compute_partitions(goal):
partitions = [1]
for n in range(1,goal+1):
partitions.append(0)
for k in range(1,n+1):
coeff = (-1)**(k+1)
for t in [pentagonal_number(k), pentagonal_number(-k)]:
if (n-t) >= 0:
partitions[n] = partitions[n] + coeff*partitions[n-t]
return partitions
```
我改成了C++版本
```
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int mod = 998244353;
int pentagonal_number(int k) {
return static_cast<int>(k*(3*k-1) / 2);
}
vector<int> compute_partitions(int goal) {
std::vector<int> partitions(1, 1);
for (int n = 1; n <= goal; ++n) {
partitions.push_back(0);
for (int k = 1; k <= n; ++k) {
int coeff = pow(-1, k+1);
for (auto t : {pentagonal_number(k), pentagonal_number(-k)}) {
if ((n-t) >= 0) {
partitions[n] += coeff * partitions[n-t];
partitions[n] %= mod;
}
}
}
}
return partitions;
}
int main()
{
int n;
cin >> n;
vector <int> g = compute_partitions(n);
for(int i = 1; i <= n; i++)
cout << g[i] << ' ';
}
```
或者是这个稍微阳间一点点的版本（也好不到哪里去）
```
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int mod = 998244353;
int pentagonal_number(int k) {
return static_cast<int>(k*(3*k-1) / 2);
}
int main()
{
int n;
cin >> n;
vector<int> p(1, 1);
for (int i = 1; i <= n; ++i) {
p.push_back(0);
for (int k = 1; k <= i; ++k) {
int coeff = pow(-1, k+1);
for (auto t : {pentagonal_number(k), pentagonal_number(-k)}) {
if ((i-t) >= 0) {
p[i] += coeff * p[i-t];
p[i] %= mod;
}
}
}
}
for(int i = 1; i <= n; i++)
cout << p[i] << ' ';
}
```
[该问题的wiki（英）](https://en.wikipedia.org/wiki/Partition_(number_theory))
[该问题的wiki（中）](https://zh.wikipedia.org/wiki/%E6%95%B4%E6%95%B8%E5%88%86%E6%8B%86)
by Sicosuki @ 2023-10-28 17:50:49
@[Misaka_Mikoto_19090](/user/966328)
by Sicosuki @ 2023-10-28 17:52:54
@[Misaka_Mikoto_19090](/user/966328) https://oi-wiki.org/math/combinatorics/partition/
by yllcm @ 2023-10-28 18:05:54