分割函数
<p>不限每个自然数的个数:
即生成函数为
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/4dc0207a3790e07aa72ad9b113ddd7dc" alt="" /></p>
<pre><code class="language-cpp">#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const int base = 1e5;
ll temp[maxn<<1];
ll ans[maxn];
int t;
void init(){
for(int i = -1e5-1; i <= 1e5+1; i++){
temp[i+base] = 1ll*i*(3*i-1)/2;
}
ans[0] = 1;
for(int i = 1; i <= 1e5; i++){
ans[i] = 0;
for(int j = 1; j <= i; j++){
if(temp[j+base] <= i){
if(j & 1) ans[i] = (ans[i] + ans[i - temp[j+base]]) % mod;
else ans[i] = (ans[i] - ans[i - temp[j+base]]) % mod;
}else break;
if(temp[base-j] <= i){
if(j & 1) ans[i] = (ans[i] + ans[i - temp[base-j]]) % mod;
else ans[i] = (ans[i] - ans[i - temp[base-j]]) % mod;
}else break;
}
ans[i] = (ans[i] + mod) % mod;
}
}
int main(){
init();
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
printf("%lld\n", ans[n]);//ans[i]为分割函数第i个的值
}
}</code></pre>
<p>限制每个自然数最多取k-1个
生成函数为
<img src="https://www.showdoc.com.cn/server/api/attachment/visitfile/sign/d65644fef33a416fdd2bc34ac03ac9bb" alt="" /></p>
<pre><code class="language-cpp">#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const int base = 1e5;
ll temp[maxn<<1];
ll ans[maxn];
int t;
int n, k;
void init(){
for(int i = -1e5-1; i <= 1e5+1; i++){
temp[i+base] = 1ll*i*(3*i-1)/2;
}
ans[0] = 1;
for(int i = 1; i <= 1e5; i++){
ans[i] = 0;
for(int j = 1; j <= i; j++){
if(temp[j+base] <= i){
if(j & 1) ans[i] = ans[i] + ans[i - temp[j+base]];
else ans[i] = ans[i] - ans[i - temp[j+base]];
while(ans[i] < 0) ans[i] += mod;
while(ans[i] >= mod) ans[i] -= mod;
}else break;
if(temp[base-j] <= i){
if(j & 1) ans[i] = ans[i] + ans[i - temp[base-j]];
else ans[i] = ans[i] - ans[i - temp[base-j]];
while(ans[i] < 0) ans[i] += mod;
while(ans[i] >= mod) ans[i] -= mod;
}else break;
}
while(ans[i] < 0) ans[i] += mod;
while(ans[i] >= mod) ans[i] -= mod;
}
}
ll solve(){
ll res = ans[n];
for(int j = 1; j <= n; j++){
if(temp[j+base]*k <= n){
if(j & 1) res = res - ans[n - temp[j+base]*k];
else res = res + ans[n - temp[j+base]*k];
while(res < 0) res += mod;
while(res >= mod) res -= mod;
}else break;
if(temp[base-j]*k <= n){
if(j & 1) res = res - ans[n - temp[base-j]*k];
else res = res + ans[n - temp[base-j]*k];
while(res < 0) res += mod;
while(res >= mod) res -= mod;
}else break;
}
while(res < 0) res += mod;
while(res >= mod) res -= mod;
return res;
}
int main(){
init();
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &k);
printf("%lld\n", solve());
}
}</code></pre>
<pre><code>$$(1+x+x^2+x^3+...)(1+x^2+x^4+x^6+...)(1+x^3+x^6+...)$$
$$(1+x+x^2+...+x^k)(1+x^2+x^4+...+x^{2(k-1)})(1+x^3+x^6+...+x^{3(k-1)})$$</code></pre>