題干：

soda has a set?SS?with?nn?integers?{1,2,…,n}{1,2,…,n}. A set is called key set if the sum of integers in the set is an even number. He wants to know how many nonempty subsets of?SS?are key set.

Input

There are multiple test cases. The first line of input contains an integer?TT?(1≤T≤105)(1≤T≤105), indicating the number of test cases. For each test case:?

The first line contains an integer?nn?(1≤n≤109)(1≤n≤109), the number of integers in the set.

Output

For each test case, output the number of key sets modulo 1000000007.

Sample Input

4 1 2 3 4

Sample Output

0 1 3 7

解題報告：

? ?這應該算是多校里面的大水題了吧？（ps：當時寫的快速冪也太丑陋了吧、、、）

因為集合Ｓ中的元素是從１開始的連續的自然數，所以所有元素中奇數個數與偶數個數相同，或比偶數多一個。另外我們要知道偶數＋偶數＝偶數，奇數＋奇數＝偶數，假設現在有ａ個偶數，ｂ個奇數，則

根據二項式展開公式

以及二項式展開式中奇數項系數之和等于偶數項系數之和的定理

可以得到

最后的結果還需減去

即空集的情況，因為題目要求非空子集

所以最終結果為

部分題解來自這里

AC代碼：

#include<bits/stdc++.h> #define mod 1000000007 typedef long long ll;using namespace std; ll n; ll qpow(ll a,ll k) {ll ans = 1;while(k > 0) {if(k&1) {ans*=a;}ans%=mod;a*=a;a%=mod;k>>=1;}return ans%mod; } int main() {int t;ll ans;cin>>t;while(t--) {scanf("%lld", &n);ans = qpow(2,n%mod-1);printf("%lld\n",ans-1);}return 0; }

?

總結

以上是生活随笔為你收集整理的【 HDU - 5363】Key Set（水题，快速幂，组合数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。