BZOJ 1965 洗牌 [快速乘+快速幂] BZOJ1965: [Ahoi2005]SHUFFLE 洗牌

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll mul(ll a,ll b,ll m)  //  和快速幂思想一样，把乘数二进制分解，然后加起来
 5 {
 6     ll res=0;
 7     for (ll i=b; i; i>>=1,a=(a+a)%m)
 8       if (i&1) res=(res+a)%m;
 9     return res;
10 }
11 ll qpow(ll a,ll b,ll m)
12 {
13     ll res=1;
14     for (ll i=b; i; i>>=1,a=mul(a,a,m))
15       if (i&1) res=mul(res,a,m);
16     return res;
17 }
18 int main()
19 {
20     ll n,m,l,ans;
21     scanf("%lld%lld%lld",&n,&m,&l);
22     ans=l*qpow(n/2+1,m,n+1);
23     printf("%lld
",(ans+n+1)%(n+1));
24     return 0;
25 }