【HDU 4602】Partition

题意

给你一个数n，把它写成几个正整数相加的形式，即把n拆开成若干段，把所有可能的式子里正整数 k 出现的次数取模是多少。

分析

特判 k>=n 的情况。

k<n时：问题相当于n个点排一行，选其中连续的k个点，其他点的间隔情况有多少种。

n个点原来有n-1个两两之间的间隔，当n-k>1时，如果k个点不包含端点，那么剩下的间隔就是：n-1 -（k+1）=n-k-2。此时每个间隔，就有隔或者不隔2种情况，选这k个点的方法又有n-k-1种，所以共有2的n-k-2次方 * （n-k-1）种间隔方案。

如果包含端点，剩下的间隔就是：n-1 -k。因为两个端点，所以有2*（2的n-1-k次方）种间隔方案。

所以总共有2^n-k-2*（n-1-k）+2*2^n-1-k=（n-3-k）*2^n-k-2种方案。

注意到如果n-k=1，那么只有包含端点的情况，答案就是2，故也进行特判。

然后用快速幂取模就可以啦。

代码

#include<cstdio>
#define ll long long
ll m=1e9+7;
ll qpow(int b)
{
    ll a=2,ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%m;
        a=a*a%m;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll t,n,k;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&k);
        if(n<k)
            printf("0
");
        else if(n==k)
            printf("1
");
        else if(n-k==1)
            printf("2
");
        else
            printf("%lld
",(n-k+3)*qpow(n-k-2)%m);
    }
    return 0;
}