SPOJ VECTAR5 推公式

Count Subsets

You are given a set S = {1, 2, 3, ..., n}. Your task is simple. You have to calculate the number of ways of selecting non empty subsets A and B such that A is not a subset of B and B is not a subset of A. Since answer can be large output the result mod 10^9 + 7.

Input

First line of input contains single integer t denoting number of test cases.

Next t lines contain a single integer n.

Output

For each test case output answer to problem by taking mod with 10^9 + 7.

Constraints

1 <= t <= 100000

1 <= n <= 1000000

Example

SAMPLE INPUT: 2 4 8 SAMPLE OUTPUT: 110 52670

题意：对于一个集合S = {1, 2, ..., n}, 问选择一个非空集合A，一个非空集合B， A和B都是S的子集，A不是B的子集，且B不是A的子集的方案数有多少，对答案mod1e9+7。

题解：A的取法有(2^n-1)种  B的取法也有(2^n-1)种

那么所有取法是(2^n-1)*(2^n-1)种

我们先不考虑A==B

那么A是B的子集的情况有(C(n,1)*(2^1-1)+C(n,2)*(2^2-1)+...+C(n,n)*(2^n-1))种

因为AB有对称性  所以再乘个2

因为上面的式子包含了A==B  所以我们再把A==B加上就行了  有(2^n-1)种

现在的问题是上面的式子怎么求和

可以先把-1提出来

C(n,1)*2^1+C(n,2)*2^2+...+C(n,n)*2^n   -   (C(n,1)+C(n,2)+...+C(n,n))

现在就不难看出来了

二项式的展开

所以左边就等于3^n-1  右边等于 2^n-1

然后求和取模就行了

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const ll mod=1000000007; ll quick(ll a,ll k){ ll ans=1; while(k){ if(k&1)ans=ans*a%mod; k/=2; a=a*a%mod; } return ans; } int main(){ ll t; scanf("%lld",&t); while(t--){ ll i,n; scanf("%lld",&n); ll ans=quick(quick(2,n)-1,2); ll t1=(quick(3,n)-quick(2,n))*2%mod; ans=ans-t1+quick(2,n)-1; ans=(ans%mod+mod)%mod; printf("%lld\n",ans); } return 0; }