首页 > ACM题库 > HDU-杭电 > HDU 4602-Partition-递推-[解题报告]HOJ
2015
09-17

HDU 4602-Partition-递推-[解题报告]HOJ

Partition

问题描述 :

Define f(n) as the number of ways to perform n in format of the sum of some positive integers. For instance, when n=4, we have
  4=1+1+1+1
  4=1+1+2
  4=1+2+1
  4=2+1+1
  4=1+3
  4=2+2
  4=3+1
  4=4
totally 8 ways. Actually, we will have f(n)=2(n-1) 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 2(n-1) ways. In the example above, number 1 occurs for 12 times, while number 4 only occurs once.

输入:

The first line contains a single integer T(1≤T≤10000), indicating the number of test cases.
Each test case contains two integers n and k(1≤n,k≤109).

输出:

The first line contains a single integer T(1≤T≤10000), indicating the number of test cases.
Each test case contains two integers n and k(1≤n,k≤109).

样例输入:

2
4 2
5 5

样例输出:

5
1

/*
分析:
    2013multi第一场c题,递推找规律都行。
    打个表就能看出来规律了,递推的过程完全就是高中时候数学某
种经典题的原题= =I 。

                                          2013-07-23
*/

#include"iostream"
#include"cstdio"
#include"cstring"
using namespace std;
const int mod=1000000007;

__int64 sp(__int64 a,__int64 b)
{
	__int64 ans=1;
	while(b)
	{
		if(b%2)	ans=(ans*a)%mod;
		b/=2;
		a=(a*a)%mod;
	}
	return ans%mod;
}
__int64 solve(int x)
{
	__int64 ans;
	if(x==1)	return 1;
	if(x==2)	return 2;
	if(x==3)	return 5;
	ans=((2*sp(2,x-2))%mod+((x-2)*sp(2,x-3))%mod)%mod;
	return ans;
}
int main()
{
	int T;
	int n,k;
	int x;
	cin>>T;
	while(T--)
	{
		scanf("%d%d",&n,&k);
		if(k>n)	{printf("0\n");continue;}
		x=n;
		x-=(k-1);
		printf("%I64d\n",solve(x));
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/9427583