ACM-ICPC 2018 焦作赛区网络预赛 G. Give Candies（大数幂，欧拉降幂）

题目链接：https://nanti.jisuanke.com/t/31716

样例输入 
1
4
样例输出 
8

题意：n个小朋友n个糖果，从第一个小朋友开始给糖果，至少给一颗糖果，直到糖果给完，问有几种分糖果的方法

思路：很容易看出来答案是2^（n-1），问题是n很大，所以要用大数，并且用到欧拉降幂，因为取模的mod=1e9+7，是素数，所以欧拉值为mod-1，2^n=2^(mod-1+n%(mod-1))，大数取模一位一位的取就可以了。由于大数的减一写起来不方便，所以直接求了2^n最后答案乘上2的逆元，即除了2

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define maxn 300005
using namespace std;
typedef long long ll;

const ll  mod=1e9+7;
ll mo(ll a,ll pp){
    if(a>=0&&a<pp)return a;
    a%=pp;
    if(a<0)a+=pp;
    return a;
}
ll powmod(ll a,ll b,ll pp){
    ll ans=1;
    for(;b;b>>=1,a=mo(a*a,pp)){
        if(b&1)ans=mo(ans*a,pp);
    }
    return ans;
}
ll inv1(ll b){
	return powmod(b,mod-2,mod);
}

char s[100005];


int main(){
	int t;
	scanf("%d",&t);
	scanf("\n");
	while(t--){
		gets(s);
		ll k=strlen(s),sum=0;
		for(int i=0;i<k;i++){
			sum=(sum*10+s[i]-'0')%(mod-1);
		}
		sum=sum+mod-1;
		cout<<powmod(2,sum,mod)%mod*inv1(2)%mod<<endl;
	}
	return 0;
}