ACM-ICPC 2018 焦作赛区网络预赛 Give Candies 题解

ACM-ICPC 2018 焦作赛区网络预赛 Give Candies

n个糖果分给n个小朋友
从1到n个小朋友依次给，每次随机给个数，至少一个，知道没有糖果为止。
问糖果的分布情况方案数。
输出方案数mod $1 0^{9} + 7$

考虑只有前i个小朋友得到糖的情况，于是等价于将n个糖果分为i堆，插板法易得方案数是 $(\frac{n - 1}{i - 1})$
总方案数 $\sum_{i = 1}^{n} (\frac{n - 1}{i - 1}) = 2^{n - 1}$
$2^{n - 1} m o d 1000000007$
$a^{n} m o d p$
p是质数，只是n很大
$a^{n} \equiv a^{n m o d ϕ (p)} (m o d p)$
依据是费马-欧拉定理

更一般的情况简记

事实上，更为一般的是:
$g c d (a, c) = 1 \Rightarrow a^{b} \equiv a^{b m o d ϕ (c)} (m o d c)$
如果a,c不互素呢？
$b > ϕ (n) \Rightarrow a^{b} \equiv a^{b m o d ϕ (c) + ϕ (c)} (m o d c)$
如果 $b \leq ϕ (n)$ ；那就不用换了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
const ll mod = 1e+9+7; // is prime
const ll phi_mod = mod-1;

// pre: mod != 0, <a,n>!=<0,0> n>=0
ll mlt(ll a, ll n, ll mod) {
    if (n == 0)
        return 1;
    ll t = 1;
    a %= mod;
    while (n > 1) {
        if (n&1)
            t = (t*a)%mod;
        a = (a*a)%mod;
        n >>= 1;
    }
    return (t*a)%mod;
}
string s;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        cin>>s;
        n = 0;
        for (auto x : s)
            n = ((n*10)+x-'0')%phi_mod;
        n = (n-1+phi_mod)%phi_mod;
        cout<<mlt(2ll,n,mod)<<endl;
    }
    return 0;
}