题目描述：

　　

这道题，我们首先一眼瞪出来一个规律：对于一个位置为i的牌，在1次洗牌后，他的位置处于(i*2)%(n+1) 的位置

那么，显然的，对于M次洗牌 我们只需要求出2的m次方，这个我们采用快速幂。

那么 我们的主要目的，就是找到一个X 使  

成立

那么 我们就需要用到2^m的逆元，这个n+1不一定是素数，有点不太好搞啊……

 

不过没关系！我们看到，这个数字的底数为2 而n+1一定为奇数·（n为偶数） 下面请记住一个结论

对于一个奇数n ,2在膜n意义下的逆元是(n-1)/2+1 这个很好证明，把它乘2就是n+1 膜n意义下为1 符合逆元的定义

 

于是这道题就变得简单起来了：求n/2+1的m次方（mod n+1) 把它与l相乘，得到的就是x了！

 

上代码：

#include
      
       #include
       
        typedef unsigned long long ull;ull n,m,l;ull qpow(ull a,ull m) {    ull base = a,ans=1;    while(m) {#ifdef DEBUG        printf("%llu %llu",ans,base);#endif        if(m&1) (ans*=base)%=n+1;        (base*=base)%=n+1;m>>=1;    }    return ans;}ull after(ull n,ull p) {    return n*p%(n+1);}ull inv(ull p) {    return qpow(p,n-1);}int main() {    scanf("%llu%llu%llu",&n,&m,&l);    ull p = qpow((n/2)+1,m);#ifdef DEBUG    printf("%llu\n",p);#endif    printf("%llu",l*p%(n+1));    return 0;}