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 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;
}