P2054 [AHOI2005]洗牌
扩展欧拉定理求逆元
$1 2 3 4 5 6$
$4 1 5 2 6 3$
$2 4 6 1 3 5$
$1 2 3 4 5 6$
手推一下样例，你就会发现是有规律的：
位置->位置
$1->2$
$2->4$
$3->6$
$4->1$
$5->3$
$6->5$
规律显然，位于位置$x$的数，进行一次洗牌操作位置就会变成$x*2\%(n+1)$
那么位于$x$的数，经过$m$次操作，位置就会变成$x*2^m\%(n+1)$
那么可以列出一下同余方程
$x*2^m≡k(mod(n+1))$
然后就比较显然了，只有一个未知数$x$，扩展$gcd$好了，=_=，博主太蒟，没有看懂
另一种解释方法是：
变换一下得：$x≡k*{2^{m}}^{-1}(mod(n+1))$
问题就转换成了求解${2^{m}}$在$\%(n+1)$意义下的逆元，还是$exgcd$
$ans={2^{m}}^{-1}*l\%(n+1)$
#include<iostream>
#include<cstdio> #define LL long long
using namespace std; LL n,m,l;
LL pow(LL a,LL b){
LL s=;
for(;b;b>>=,a=a*a%(n+))
if(b&) s=s*a%(n+);
return s;
} LL exgcd(LL a,LL b,LL &x,LL &y){
if(!b){x=,y=;return a;}
LL gc=exgcd(b,a%b,x,y);
LL tmp=x;x=y;y=tmp-a/b*y;
return gc;
} int main()
{
scanf("%lld%lld%lld",&n,&m,&l);
LL m_2=pow(,m);
LL x,y;
exgcd(m_2,n+,x,y); printf("%lld\n",(x*l%(n+)+(n+))%(n+)); return ;
}