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

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

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

考虑只有前i个小朋友得到糖的情况，于是等价于将n个糖果分为i堆，插板法易得方案数是 $\left(\frac{n-1}{i-1}\right)$(i−1n−1​)
总方案数 ${\sum }_{i=1}^n\left(\frac{n-1}{i-1}\right)=2^{n-1}$∑i=1n​(i−1n−1​)=2n−1
2n−1mod1000000007
anmodp
p是质数，只是n很大
an≡anmodϕ(p)(modp)
依据是费马-欧拉定理

更一般的情况简记

事实上，更为一般的是:
gcd(a,c)=1⇒ab≡abmodϕ(c)(modc)
如果a,c不互素呢？
b>ϕ(n)⇒ab≡abmodϕ(c)+ϕ(c)(modc)
如果 $b\le \varphi \left(n\right)$b≤ϕ(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;
}