POJ 3734 推公式

/*
不做任何限制的组合数是4^n,减去出现奇数个绿色或红色球的情况。思路是从n个球中跳出k个球(k>=1 && k <=n)去染绿色和红色，剩下的球的情况自然是2^(n-k)，
问题转化为求k个球染两种颜色的组合数，且必有一种球染奇数。、下面公式给出取k个球染红绿且非法的情况
2(C(k,1)+C(k,3)+C(k,5)...)。。。*C(n,k)*2^(n-k) 当k为奇数，此式刚好是2^k,当k为偶数，此式变成2^(k-1)
于是推出公式为4^n - 2^n * C(n,1) - 2^(n-1)*C(n,2) - 2^n*C(n,3)...
即 4^n - 2^n*2^(n-1) - 2^(n-1)(C(n,2)+C(n,4)...)
得 2^n - 2^(n-1) * (2^(n-1)-1)
化为 2^(n-1) * ( 1 + 2^(n-1))
剩下的就是二分求幂了，nima推了一个小时。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define modx 10007
using namespace std;int t, n;long long quick_pow(int a,int n)
{long long result;if(n == 1) return a;if(!n)    return 1;long long mid = quick_pow(a,n/2);if(n%2) result = mid*mid%modx*a%modx;else    result = mid*mid%modx;return result;
}
int main()
{scanf("%d", &t);while(t--){scanf("%d", &n);long long f = quick_pow(2,n-1);printf("%lld\n", f*(1+f)%modx);}
}