游客 注册 | 登录
中文 | En

3699 - 你猜D

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

我们定义一个数列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出现的次数是多少。

题目输入

输入文件包含多组测试数据。第一行，给出一个整数 T（T<=20），为数据组数。

接下来有一行，分别输入两个数n,k（1<=n,k<=10^9）

题目输出

输出结果并对1e9+7取余

输入/输出样例

输入格式

2
4 2
5 5

输出格式

5
1

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;
}
请先登陆