HDU4704 (Sum)[费马小定理]

发表于 | 更新于 | | 阅读次数：

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4704

求解S(k)，把N分成k个数之和，问有多少种方案，这个问题等价于n个皮球分成k堆有多少种方案，套用高中学的隔板法得到公式为C(n-1, k-1)。
此时S(1) + S(2) + … + S(n) = C(n-1, 0) + C(n-1, 1) + … + C(n-1, n-1) = 2^(n-1)。套用费马小定理求解即可。

费马小定理：a^(n-1)≡1 (mod n), n为质数。
推论：x^y≡x^(y%(n-1)) (mod n)，n为质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int M = 1000000007;
char s[100009];
ll pow_mod(ll x,ll y) {
	ll ans=1;
	for(ll i=x;y;y>>=1,i=(i*i)%M) {
		if(y&1) ans=(ans*i)%M;
	}
	return ans;
}
int main() {
	while(~scanf("%s",s)) {
		ll y=0;
		for(int i=0;s[i]!='\0';i++) {
			y=(y*10%(M-1) + s[i]-'0')%(M-1);
		}
		printf("%lld\n",pow_mod(2,y-1));
	}
}