首页 > 代码库 > hdu 4602 Partition (概率方法)
hdu 4602 Partition (概率方法)
Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2472 Accepted Submission(s): 978
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.
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).
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
2 4 2 5 5
Sample Output
5 1
对于1 <= k < n,我们可以等效为n个点排成一列,并取出其中的连续k个,这连续的看K个两端断开;
1、若取得是这K个点包括端点(我们只考虑一个端点的情况),还剩下(n-k-1)个间隔,
每个间隔有断开和闭合两种状态,故有2^(n-k-1),最后乘以2;
2、若取得是这K个点不包括端点,这连续的K个点有(n-k-1)种取法,还剩下(n-k-2)个间隔,
故有2^(n-k-2)*(n-k-1);
总计2 ? 2^(n – k ? 1) + 2^(n – k ? 2) ? (n – k ? 1) = (n – k + 3) * 2^(n – k ? 2)。
#include"stdio.h" #include"string.h" #include"queue" #include"vector" #include"algorithm" using namespace std; #define LL __int64 const int mod=1000000007; int main() { int T,i,n,k; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); if(n<k) printf("0\n"); else if(n==k) printf("1\n"); else { LL d=n-k,s1,t; if(d==1) printf("2\n"); else { s1=d+3; d-=2; LL aa=2,tmp=1; while(d) { if(d&1) tmp*=aa; d/=2; aa=(aa*aa)%mod; tmp%=mod; } printf("%I64d\n",(tmp*s1)%mod); } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。