Problem Description
Given n, k, calculate the number of different (unordered) partitions of n such that no part is repeated k or more times.
Input
First line, number of test cases, T.
Following are T lines. Each line contains two numbers, n and k.
1<=n,k,T<=10
5
Output
T lines, each line contains answer to the responding test case.
Since the numbers can be very large, you should output them modulo 10
9+7.
Sample Input
4 4 2 4 3 4 4 4 5
Sample Output
2 4 4 5
生成函数+五边形数定理+分割函数
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 200005;
const int base = 1000000007;
int f[maxn], p[maxn], n, T, k;
void init()
{
int n = 1000;
for (int i = f[0] = 1; i <= n; i++)
{
f[i + i - 1] = (i * (i + i + i - 1) >> 1) % base;
f[i + i] = (i * (i + i + i + 1) >> 1) % base;
}
for (int i = p[0] = 1; i < maxn; i++)
{
p[i] = 0;
for (int j = 1, k = -1; i >= f[j]; j++)
{
if (j & 1) k *= -1;
(p[i] += k * p[i - f[j]]) %= base;
}
p[i] = (p[i] + base) % base;
}
}
int work(int n, int k)
{
int ans = p[n];
for (int i = 1, j = 1; f[i] * k <= n; i++)
{
if (i & 1) j *= -1;
(ans += j * p[n - f[i] * k]) %= base;
}
return (ans + base) % base;
}
int main()
{
init();
scanf("%d", &T);
while (T--) scanf("%d%d", &n, &k), printf("%d\n", work(n, k));
return 0;
}