BZOJ 1965

传送门

观察发现每次洗牌后编号为$x$的牌会跑到$2\cdot x\ mod(n+1)$的位置上

那么洗牌$m$次后就会跑到$2^m\cdot x\ mod(n+1)$的位置上

设洗牌$m$次后跑到$1$号位的牌为$x$，则$2^m\cdot x\equiv 1(mod\ n+1)$

即为$2^m\cdot x+(n+1)\cdot y=1$

然后拿扩展欧几里得解出$x$后第$L$张就是$x\cdot L\ mod\ (n+1)$

注意$x$可能为负，要所以特判答案为负的情况

program bzoj_1965;
var n,m,l,p,mo,x,y,g,ans:int64;
 
function qp(x,k:int64):int64;
var p:int64;
begin
  qp:=1;
  p:=x;
  while k<>0 do
  begin
    if k and 1=1 then qp:=(qp*p)mod mo;
    p:=(p*p)mod mo;
    k:=k>>1;
  end;
end;
 
function exgcd(a,b:int64):int64;
var t,g:int64;
begin
  if b=0 then
  begin
    x:=1;
    y:=0;
    exit(a);
  end;
  g:=exgcd(b,a mod b);
  t:=x;
  x:=y;
  y:=t-(a div b)*y;
  exit(g);
end;
 
begin
  readln(n,m,l);
  mo:=n+1;
  p:=qp(2,m);
  g:=exgcd(p,mo);
  ans:=(x*l mod mo+mo)mod mo;
  writeln(ans);
end.