Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2635 Accepted Submission(s): 1052
Problem Description
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.
Input
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).
Output
Output the required answer modulo 109+7 for each test case, one per line.
Sample Input
Sample Output
Source
Recommend
liuyiding | We have carefully selected several similar problems for you:
5193 5192 5191 5190 5189
1 2 3 4 5
1 1 2 5 12 28
2 1 2 5 12
3 1 2 5
4 1 2
5 1
规律：2^(m-3)*(m-2). m=n-k+1
ac代码
#include<stdio.h>
#include<string.h>
#define mod 1000000007
__int64 qpow(__int64 a,__int64 b)
{
__int64 ans=1;
while(b)
{
if(b&1)
ans=(ans*a)%mod;
a=(a*a)%mod;
b/=2;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
__int64 n,k;
scanf("%I64d%I64d",&n,&k);
if(k>n)
{
printf("0\n");
continue;
}
if(n-k+1<=2)
{
printf("%d\n",n-k+1);
}
else
{
printf("%I64d\n",(qpow(2,n-k-2)*(n-k+3))%mod);
}
}
}
HDOJ 题目4602 Partition（找规律，快速幂）
原文：http://blog.csdn.net/yu_ch_sh/article/details/44539185
