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$可能为负,要所以特判答案为负的情况


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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.