3699 - 你猜D
我们定义一个数列F(n)代表n的有序拆分数：
比如
3=3
3=1+2
3=2+1
3=1+1+1
3的有序拆分数为4种。
再比如
4=4
4=1+3
4=3+1
4=2+2
4=1+1+2
4=1+2+1
4=2+1+1
4=1+1+1+1
4的有序拆分数有8种，当然我们很容易发现F(n)=2^(n-1)，所以咱们的题目肯定不可能是这么简单的。现在我想问的是，给定任意两个数n和k，求n的所有拆分情况中，k出现的次数是多少。
Input
输入文件包含多组测试数据。第一行，给出一个整数 T（T<=20），为数据组数。
接下来有一行，分别输入两个数n,k（1<=n,k<=10^9）
Output
输出结果并对1e9+7取余
Examples
Input
2 4 2 5 5
Output
5 1
Hint
n=4的拆分数的情况上面给出了，2出现的次数显而易见为5次
n=5的拆分数更多，但是5出现的次数显然只有5=5这一种情况里面会出现,所以输出1.
Solution C++
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const long long mod=(long long )(1e9+7); int n,k; long long power(long long a,long long p) { long long res=1; while(p) { if(p&1) res=(a*res)%mod; a=(a*a)%mod; p>>=1; } return res; } long long solve(long long x) { long long res; if(x==1) return 1; if(x==2) return 2; if(x==3) return 5; res=(power(2,x-1)%mod+((x-2)*power(2,x-3)%mod))%mod; return res; } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); if(k>n) { printf("0\n"); continue; } int x=n; x-=(k-1); printf("%lld\n",solve(x)); } return 0; }
Hint
n=4的拆分数的情况上面给出了，2出现的次数显而易见为5次
n=5的拆分数更多，但是5出现的次数显然只有5=5这一种情况里面会出现,所以输出1.