HDU-5363-快速幂-组合数公式

发布于 2019-06-08  932 次阅读


问题传送门

问题描述:

第一行输入一个T,(1≤T≤105) 表示有T次询问。

每次询问有一个整数 n , 表示一个集合 1,2,3,...... n

问:这个集合中有几个非空子集,这个子集的所有元素和是偶数。

输出:满足条件的子集的个数对1000000007 取模。

分析:

  1. 任意个偶数的和是偶数
  2. 偶数个奇数的和是偶数
  3. 任意个偶数+偶数个奇数的和是偶数

对于集合 {1,2,3,....., n},设偶数有 a 个,奇数有 b 个。 所以下面公式把所有情况都包括了:

把上面公式化简后是

然后要减去0个偶数0个奇数的情况

就是答案。

因为n很大, 所以要用到快速幂算法

虽然有取模运算,但是中间的过程还是会超int,所以要用long long

下面是代码:

#include <iostream>
#include <cmath>

using namespace std;

typedef long long LL ;

const int M = 1000000007;
const int N = 1e5; 
int a[N + 1];

LL Pow(int a, int b)
{
  LL ans = 1, t = a;
  while(b)
  {
    if (b&1) ans = ans*t%M;
    t = t*t%M;
    b >>= 1;
  }
  return ans;
}
int main()
{
  LL ans = 0;
  int n, a;
  int e = 0, o = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a;
    ans = Pow(2, a-1) -1 ;
    cout << ans << endl;
  }	
  return 0;
}

Simple And Clear