hdu 4602 Partition 数学（组合-隔板法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4602

我们可以特判出n<=k的情况。

对于1<=k<n，我们可以等效为n个点排成一列，并取出其中的连续k个点。下面分两种情况考虑：

第一种情况，被选出的不包含端点，那么有(n–k−1)种情况完成上述操作，剩下未被圈的点之间还有(n–k−2)个位置，可以在每个位置断开，所以共2^(n−k−2)∗(n−k−1)种方法。

第二种情况，即被选出的包含端点，那么有2种情况，并且剩余共(n–k−1)个位置，所以共2∗2^(n–k−1)种方法。

总计2∗2^(n–k−1)+2^(n–k−2)∗(n–k−1)=(n–k+3)*2^(n–k−2)。

 1 #include<cstdio>
 2 using namespace std;
 3 const long long moder = 1e9 + 7;
 4 
 5 long long power(long long t){
 6     if(t == 0) return 1;
 7     long long ans = power(t/2) % moder;
 8     ans = ans * ans % moder;
 9     if(t % 2)  ans = ans * 2 % moder;
10     return ans;
11 }
12 int main()
13 {
14     int T;
15     scanf("%d",&T);
16     while(T--){
17         int n,k;
18         scanf("%d%d",&n,&k);
19         if(k>n) printf("0\n");
20         else if(k == n) printf("1\n");
21         else if(n - k == 1) printf("2\n");
22         else{
23             long long int ans = (((n-k+3)%moder)* (power(n-k-2)%moder))% moder ; 
24             printf("%I64d\n",ans);
25         }
26     }
27 }

View Code

优质内容筛选与推荐>>
1、This function has none of DETERMINISTIC, NO SQL, or READS SQL DATA in its declaration and binary lo的解决办法
2、python学习第二天
3、20189217 2018-2019-2 《密码与安全新技术专题》第9周作业
4、MySQL(3)---MySQL优化
5、Oracle 游标

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看