Problem Description
Define f(n) as the number of ways to perform n in format of the sum of some positive integers. For instance, when n=, we have
=+++
=++
=++
=++
=+
=+
=+
=
totally ways. Actually, we will have f(n)=(n-) after observations.
Given a pair of integers n and k, your task is to figure out how many times that the integer k occurs in such (n-) ways. In the example above, number occurs for times, while number only occurs once.
Input
The first line contains a single integer T(≤T≤), indicating the number of test cases.
Each test case contains two integers n and k(≤n,k≤).
Output
Output the required answer modulo + for each test case, one per line.
Sample Input
Sample Output
Source
题目大意：将一个数 n 拆分，问所有的拆分组合中 K 出现了几次。
思路：
列出了 n=5 时 5,4,3,2,1 出现的次数为 1 2 5 12 28
f[n+1]=3*f[n]-f[n-1]-f[n-2]-..f[1]
f[n]=3*f[n-1]-f[n-2]-..f[1]
==> f[n+1]=4*f[n]-4*f[n-1]
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
#include <stack>
using namespace std;
#define PI acos(-1.0)
#define max(a,b) (a) > (b) ? (a) : (b)
#define min(a,b) (a) < (b) ? (a) : (b)
#define ll long long
#define eps 1e-10
#define MOD 1000000007
#define N 1000000
#define inf 1e12
ll n,k;
struct Matrix{
ll mp[][];
};
Matrix Mul(Matrix a,Matrix b){
Matrix res;
for(ll i=;i<;i++){
for(ll j=;j<;j++){
res.mp[i][j]=;
for(ll k=;k<;k++){
res.mp[i][j]=(res.mp[i][j]+(a.mp[i][k]*b.mp[k][j])%MOD+MOD)%MOD;
}
}
}
return res;
}
Matrix fastm(Matrix a,ll b){
Matrix res;
memset(res.mp,,sizeof(res.mp));
for(ll i=;i<;i++){
res.mp[i][i]=;
}
while(b){
if(b&){
res=Mul(res,a);
}
a=Mul(a,a);
b>>=;
}
return res;
}
int main()
{
ll t;
scanf("%I64d",&t);
while(t--){
scanf("%I64d%I64d",&n,&k);
if(k>n){
printf("0\n");
continue;
}
ll tmp=n-k+;
if(tmp==){
printf("1\n");
continue;
}
if(tmp==){
printf("2\n");
continue;
}
if(tmp==){
printf("5\n");
continue;
} Matrix ttt;
ttt.mp[][]=;
ttt.mp[][]=-;
ttt.mp[][]=;
ttt.mp[][]=; ttt=fastm(ttt,tmp-); Matrix cnt;
cnt.mp[][]=;
cnt.mp[][]=;
ttt=Mul(ttt,cnt);
printf("%I64d\n",ttt.mp[][]); }
return ;
}