题目描述：
这道题，我们首先一眼瞪出来一个规律：对于一个位置为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<cstdio> #include<cstring> 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; }
【BZOJ1956】[Ahoi2005]SHUFFLE 洗牌
原文：https://www.cnblogs.com/Syameimaru/p/9301727.html
