【HDU 4602】Partition

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

分析

特判 k>=n 的情况。

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

【HDU 4602】Partition

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次方)种间隔方案。

所以总共有2n-k-2*(n-1-k)+2*2n-1-k=(n-3-k)*2n-k-2种方案。

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

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

代码

#include<cstdio>
#define ll long long
ll m=1e9+;
ll qpow(int b)
{
ll a=,ans=;
while(b)
{
if(b&)ans=ans*a%m;
a=a*a%m;
b>>=;
}
return ans;
}
int main()
{
ll t,n,k;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&k);
if(n<k)
printf("0\n");
else if(n==k)
printf("1\n");
else if(n-k==)
printf("2\n");
else
printf("%lld\n",(n-k+)*qpow(n-k-)%m);
}
return ;
}
上一篇:hdu 4602 Partition 矩阵快速幂


下一篇:hdu 4602 Partition