题意为将n划分为同一个数字出现不超过k-1次的划分方法总数。
对于一般的整数划分,n的生成函数p[n]为:
(1 + x + x^2 + ... )(1 + x^2 + x^4 + ...)(1 + x^3 + x^6 + ... )...表达式最终x^n的系数。
解释:
(1 + x + x^2 + ... )表示1取两次就是x^2,取三次就是x^3...
(1 + x^2 + x^4 + ... )表示2取两次就是x^4,取三次就是x^6...
(1 + x^3 + x^6 + ... )表示3取两次就是x^6,取三次就是x^9...
而(1 + x + x^2 + ... + x^n)在x < 1,n趋向∞时收敛于1/(1 - x);
(1 - x)(1 - x^2)(1 - x^3)...的简便计算方法:五边形数定理
即(1 - x)(1 - x^2)(1 - x^3)... = (1 - x - x^2 + x^5 + x^7 - x^12... )
令Φ(x) = (1 - x)(1 - x^2)(1 - x^3)...,显然[Φ(x)]^(-1) = Σp[n]x^n。
观察到x^i(i > 0)的系数为0,对比系数可得:
p[n]*x^n - x*p[n-1]*x^(n-1) - x^2*p[n-2]*x^(n-2) + x^5*p[n-5]*x^(n-5).... = 0*x^n
即p[n] = p[n-1] + p[n-2] - p[n-5] - p[n-7] + p[n-12] +...
那么对于题目所求结果的母函数p'[n]应该是:
(1 + x + x^2 + ... + x^(k-1))(1 + x^2 + x^4 + ... + x^2(k-1))...中最终x^n的系数。
其中:
(1 + x + x^2 + ... + x^(k-1))(1 + x^2 + x^4 + ... + x^2(k-1))...
= [(1 - x^k) / (1 - x)] * [(1 - x^2k) / (1 - x^2)] * [(1 - x^3k) / (1 - x^3)]...
=
Φ(x^k) / Φ(x)
=
Φ(x^k) * Σp[n]x^n
= (1 - x^k - x^2k + x^5k
+ x^7k - ... ) * (1 + p[1] * x + p[2] * x^2n + ...)
= Σp'[n]x^n
同理,对比系数可得:p'[n] = p[n] - p[n - k] - p[n - 2k] + p[n - 5k] + ...
#include <algorithm> #include <iostream> #include <stdlib.h> #include <stdio.h> using namespace std; #define MAXN 100010 #define LL long long #define MOD 1000000007 LL p[MAXN]; void init() { p[0] = p[1] = 1; p[2] = 2; p[3] = 3; for(int i = 4; i <= 100000; i++) { p[i] = 0; int flag = 1; for(int j = 1; ; j++) { int p1 = j * (3 * j - 1) / 2; int p2 = j * (3 * j + 1) / 2; if(p1 > i && p2 > i) break; if(p1 <= i) p[i] = (p[i] + flag * p[i - p1] + MOD) % MOD; if(p2 <= i) p[i] = (p[i] + flag * p[i - p2] + MOD) % MOD; flag *= (-1); } } } LL solve(int n, int k) { LL ret = p[n]; int flag = -1; for(int j = 1; ; j++) { int p1 = k * j * (3 * j - 1) / 2; int p2 = k * j * (3 * j + 1) / 2; if(p1 > n && p2 > n) break; if(p1 <= n) ret = (ret + flag * p[n - p1] + MOD) % MOD; if(p2 <= n) ret = (ret + flag * p[n - p2] + MOD) % MOD; flag *= (-1); } return ret; } int main() { // freopen("4658.in", "r", stdin); init(); int t, n, k; scanf("%d", &t); while(t--) { scanf("%d%d", &n, &k); printf("%I64d\n", solve(n, k)); } return 0; }