题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4658
题意：f(x) 为将 x 分成其他数和的形式的方案数．对于 t 组输入，输出 f(xi, k), 其中 k 表示 xi 分解的数出现的次数不超过 k 次．
思路：在 hdu4651(http://www.cnblogs.com/geloutingyu/p/7599415.html) 的基础上加个限制 k.
感觉公式好难推，直接当模板用好了．
代码：
#include <iostream>
#include <stdio.h>
using namespace std; const int mod = 1e9 + ;
const int MAXN = 1e5 + ;
int f[MAXN]; void get_f(void){
f[] = ;
for(int i = ; i < MAXN; i++){
for(int j = , cnt = ; i - ( * j * j - j) / >= ; j++, cnt *= -){
int cc = * j * j;
f[i] += f[i - (cc - j) / ] * cnt;
f[i] %= mod;
f[i] = (f[i] + mod) % mod;
if(i >= (cc + j) / ){
f[i] += f[i - (cc + j) / ] * cnt;
f[i] %= mod;
f[i] = (f[i] + mod) % mod;
}
}
}
} int solve(int n, int k){
int ans = f[n];
for(int i = , cnt = -; n - k * ( * i * i - i) / >= ; i++, cnt *= -){
ans += f[n - k * ( * i * i - i) / ] * cnt;
ans %= mod;
ans = (ans + mod) % mod;
if(n - k * ( * i * i + i) / >= ){
ans += f[n - k * ( * i * i + i) / ] * cnt;
ans %= mod;
ans = (ans + mod) % mod;
}
}
return ans;
} int main(void){
get_f();
int t, x, k;
scanf("%d", &t);
while(t--){
scanf("%d%d", &x, &k);
printf("%d\n", solve(x, k));
}
return ;
}