费马小定理 + 快速幂 Give Candies
There are N children in kindergarten. Miss Li bought them N candies. To make the process more interesting, Miss Li comes up with the rule: All the children line up according to their student number (1…N), and each time a child is invited, Miss Li randomly gives him some candies (at least one). The process goes on until there is no candy. Miss Li wants to know how many possible different distribution results are there.
Input
The first line contains an integer T, the number of test case.
The next T lines, each contains an integer N.
1 ≤ T ≤ 100
1 ≤ N ≤ 10^100000
Output
For each test case output the number of possible results (mod 1000000007).
样例输入复制
1
4
样例输出复制
8
题目来源
解题思路：
可知有n个糖和无限个学生，并且分到的每个学生至少分一个糖果。
那么不难想到，第一个学生必定要分到第一个糖果，第二个糖果可以给当前的学生或者下一个学生，有两种分法，第三个学生同样可以分给当前学生或下一个学生，有两种分法......
即总共有： $$1*2^{(n-1)}$$ 种分法
所以该题目要求的就是 $$2^{(n-1)}$$。( 实际是：$$2^{(n-1)}\%mod$$ )
但是问题是n比较大，是无法直接计算的，那么我们怎么才能快速计算出 $$2^{(n-1)}\%mod$$ 呢？
此处我们需要用到费马小定理。
-------------------------------------------------费马小定理简述-----------------------------------------------------
文章来自于百度百科，有部分改动。
引理1．
若a,b,c为任意3个整数,m为正整数，且(m,c)=1，则当a·c≡b·c(mod m)时，有a≡b(mod m)。
(m,c)=1 意思是m与c互质。
证明：a·c≡b·c(mod m)可得ac–bc≡0(mod m)可得(a-b)·c≡0(mod m)。因为(m,c)=1即m,c互质，c可以约去，a– b≡0(mod m)可得a≡b(mod m)。 [1]
引理2．
设m是一个整数且m>1，b是一个整数且(m,b)=1。
如果a[1],a[2],a[3],a[4],…a[m]是模m的一个完全剩余系，则b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也构成模m的一个完全剩余系。
证明:若存在2个整数b·a[i]和b·a[j]同余即b·a[i]≡b·a[j] (mod m) (i>=1 && j>=1)，根据引理1则有a[i]≡a[j] (mod m)。根据完全剩余系的整数可知这是不可能的，因此不存在2个整数b·a[i]和b·a[j]同余。
所以b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]构成模m的一个完全剩余系。
构造素数 
因为 
也是p的一个剩余系（百度百科此处也为完全剩余系）。由剩余系的性质，
即
易知 
这样就证明了费马小定理。
===================================================================================
好，看完了百度“官方”的瞎逼操作，来让我们看一下中科院的大佬们怎么讲费马小定理的：
由多项式展开或杨辉三角形可知，下面这个式子可以整除p
$$ (x+1)^p = C^0_p x^p + C^1_{p-1} x^{p-1} + \dots + C^p_0 x^0 $$
$$ ((x+1)^p-x^p-1) \% p = 0 \tag{1} $$
费马小定理我们要证明 n^p-n 可以整除p ,即
$$ (n^p-n) \% p = 0 \tag{2} $$
使用归纳证明：
可知当 n = n 时, 若 @2 成立
又因为@1 可以整除p， 那么：
$$ (n^p-n)+( (n+1)^p - n^p - 1) \\ = (n+1)^p - (n+1) \tag{3} $$
也可以整除p
即 @3 % p = 0
带入n=1成立，至此费马小定理得证。
$$ (n^p-n) \% p = 0 $$
即: $$ (n*(n^{(p-1)} - 1)) \% p = 0 $$
$$ n^{(p-1)} \equiv 1 (mod p) $$
所以 $$ n^{(p-1)} \equiv 1 (mod p) $$
由费马小定理可知
即a^(p-1)与1关于p同余。
即a^(p-1)%p=1;
我们可以把一个比较大的a^n拆成如下形式：
a^n=a^(p-1)a^(p-1)a^(p-1)...*a^x；
a^n%p=(a^(p-1)%p)(a^(p-1)%p)(a^(p-1)%p)....(a^x%p);//x为将n按照一份p-1的方式分，分剩下的。
由上述推导我们可知：a^n%p=(1)(1)(1)....(a^x%p);
即：a^n%p=a^(n%(p-1))%p;
那么我们首先需要求n%(p-1);
对于这样大的一个n我们可以采用边输入边求余的方式得到n%p-1;
String s;
long long ans=0;
for(int i=0;i!=s.size();i++)
{
ans*=10;
ans+=(s[i]-'0');
ans%=(p-1);
}
可知n%(p-1)仍然是一个很大的数字，毕竟mod=1000000007；
那么我们需要用快速幂的方法快速求出a^(n%(p-1))%p;
快速幂见我的另一篇博客：https://blog.csdn.net/o_ohello/article/details/82780667
最终代码为：
#include
using namespace std;
const long long p=1000000007;
int T;
int main()
{
scanf("%d",&T);
for(int t=0;t!=T;t++)
{
string s;
cin>>s;
long long ans=0;
for(int i=0;i!=s.size();i++)
{
ans*=10;
ans+=(s[i]-'0');
ans%=(p-1);
}
ans--;
long long base=2,answer=1;
while(ans)
{
if(ans&1)answer=answer*base%p;
base=base*base%p;
ans>>=1;
}
printf("%lld
",answer);
}
return 0;
}