洛谷 P2054 [AHOI2005]洗牌

逆元是积性函数，这道题还用了一个mul函数，防止爆long long

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll N,M,L;
ll MOD;
ll mul(ll a, ll b) {
  ll ret = 0;
  while (b) {
    if (b & 1) ret = (ret + a) % MOD;
    a = (a + a) % MOD;
    b >>= 1;
  }
  return ret % MOD;
}
ll modpow(ll a, ll b)
{
    ll ans = 1, base = a%MOD;
    while(b != 0)
    {
        if(b&1 != 0)
            ans = mul(ans,base); 
        base = mul(base,base);
        b >>= 1;
    }
    return ans%MOD;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(a==0)
    {
        x=0,y=1;
        return b;
    }
    ll d=exgcd(b%a,a,y,x);
    x-=b/a*y;
    return d;
}
int main()
{
    scanf("%lld%lld%lld",&N,&M,&L);
    MOD=N+1;
    ll x,y;
    ll index=modpow(2,M);
    exgcd(index,MOD,x,y);
    x=(x%MOD+MOD)%MOD;
    printf("%lld
",mul(L,x));
}