hdu4707 Sum 【整数和拆分 + 快速幂 + 费马小定理降幂 】

题意：

给你一个很大的n， 要你求n的拆分有几种方式， 答案模1000000007.

把n进行拆分， 可以看出n个1进行隔板， 答案就是 2 ^(n - 1)

由于n的数字较大， 用费马小定理进行降幂

a^n % p== a^(n - (p-1) - ....- (p-1)) % p = a^(n%(p-1))%p

/*
Algorithm:整数和拆分 + 快速幂 + 费马小定理降幂 
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
#define modd 1000000007
#define line printf("--------------");
using namespace std;
char str[maxn];

/*
a^(p-1) % p == 1
a^n % p == a^((n-1)%(p-1)) % p 
*/
ll ksm(ll a, ll b){
	ll ans = 1;
	while(b){
		if(b & 1){
			ans = ans * a % modd;
		}
		b = b / 2;
		a = a * a % modd;
	}
	return ans;
}
int main() {
	while(gets(str)){
		ll m = modd - 1;
		ll ans = 0;
		int len = strlen(str);
		for(int i = 0; i < len; i++){// 将输入的数字 模以 mod-1 费马小降幂 
			ans = ans * 10 + str[i] - '0';
			ans = ans % m;
		}
		ans = (ans - 1 + m) % m;
		ll t = ksm(2, ans);
		cout<<t<<endl;
	}
	return 0;
}