hdu4704——Sum

emmmmm狗屁费马小定理
我们首先定义 An=S1+S2+...+Sn A n = S 1 + S 2 + . . . + S n ，所以 An+1=S1+S2+...+Sn+Sn+1 A n + 1 = S 1 + S 2 + . . . + S n + S n + 1 ，而 Sn+1 S n + 1 表示n+1个数组成n的情况数，我们考虑第一个数为 1,2,...n 1 , 2 , . . . n ，比如第一个数是1的情况， Sn+1 S n + 1 就转化为 Sn S n ，同理，最后 Sn+1=S1+S2+...+Sn S n + 1 = S 1 + S 2 + . . . + S n ，代入前式得到， An+1=2An A n + 1 = 2 A n ，因此所求的即是 2n 2 n % m m

2n%m=(2n%(m−1)×2nm−1(m−1))%m=(2n%(m−1))%m×((2nm−1)m−1)%m=2n%(m−1))%m $2^n\%m=(2^{n\%(m-1)}\times 2^{\frac{n}{m-1}(m-1)})\%m=\left(2^{n\%(m-1)}\right)\%m\times \left(\right(2^{\frac{n}{m-1}}{)}^{m-1})\%m=2^{n\%(m-1)})\%m$

所以，最后就是将 2n%m 2 n % m 转化为 2n%(m−1)%m 2 n % ( m − 1 ) % m ，肯定快了

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100050;
const int MOD=1e9+7;
char s[N];
long long qPow(long long a,long long k){
    long long sum=1;
    while(k){
        if(k%2){
            sum=(sum*a)%MOD;
        }
        a=a*a%MOD;
        k>>=1;
    }
    return sum;
}
int main(void){
    while(~scanf("%s",s)){
        long long sum=0;
        int i=0;
        while(s[i]){
            sum=(sum*10+s[i]-'0')%(MOD-1);
            i++;
        }
        long long n=sum-1;
        printf("%lld\n",qPow(2,n));
    }
    return 0;
}