这里写图片描述

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

2 n % m = ( 2 n % ( m 1 ) × 2 n m 1 ( m 1 ) ) % m = ( 2 n % ( m 1 ) ) % m × ( ( 2 n m 1 ) m 1 ) % m = 2 n % ( m 1 ) ) % m

所以,最后就是将 2n%m 2 n % m 转化为 2n%(m1)%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;
}