HDU 4704 - Sum (费马小定理)
题意
计算一个数能被分成几部分的和。
隔板法。
$n-1$个缝，$ans = \sum C_{n-1}^{0} + C_{n-1}{1} + … + C_{n-1}{n-1} = 2^{n-1}$
因为n很大。
$2^{n-1} \bmod p = 2^{(n-1) \bmod (p-1)} \bmod p$
还是不会证。。只能记了。
代码
#include <stack>
#include <cstdio>
#include <list>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <string>
#include <map>
#include <cmath>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define SZ(x) (int)x.size()
#define Lowbit(x) ((x) & (-x))
#define MP(a, b) make_pair(a, b)
#define MS(arr, num) memset(arr, num, sizeof(arr))
#define PB push_back
#define X first
#define Y second
#define ROP freopen("input.txt", "r", stdin);
#define MID(a, b) (a + ((b - a) >> 1))
#define LC rt << 1, l, mid
#define RC rt << 1|1, mid + 1, r
#define LRT rt << 1
#define RRT rt << 1|1
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int MAXN = 62*62;
const int MOD = 1e9 + 7;
const int dir[][2] = { {-1, 0}, {0, -1}, { 1, 0 }, { 0, 1 } };
int cases = 0;
typedef pair<int, int> pii;
LL pow_mod(LL a, LL m, LL n)
{
LL ret = 1;
while (m)
{
if (m & 1) ret = ret * a % n;
a = a*a % n;
m >>= 1;
}
return ret;
}
int main()
{
ios::sync_with_stdio(0);
string num;
while (cin >> num)
{
LL n = 0;
for (int i = 0; i < SZ(num); i++)
n = (n*10 + num[i]-'0') % (MOD-1);
n--;
n = (n+MOD) % MOD;
cout << pow_mod(2, n, MOD) << endl;
}
return 0;
}