bzoj 1965: [Ahoi2005]SHUFFLE 洗牌

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #define ll long long
 5 using namespace std;
 6 ll n,m,l;
 7 void exgcd(ll a1,ll a2,ll &x,ll &y)
 8 {
 9     if(!a2)
10       {
11         x=1;
12         y=0;
13         return;
14       }
15     exgcd(a2,a1%a2,x,y);
16     ll t=x;
17     x=y;
18     y=t-a1/a2*y;
19 }
20 int main()
21 {
22     scanf("%lld%lld%lld",&n,&m,&l);
23     n++;
24     ll ans=1,k=2;
25     for(;m;)
26       {
27         if(m%2)
28           ans=(ans*k)%n;
29         k=k*k%n;
30         m/=2;
31       }
32     ll x,y;
33     exgcd(ans,n,x,y);
34     if(x<0)
35       x+=n;
36     printf("%lld\n",l*x%n);
37     return 0;
38 }