BZOJ 4002

好坑啊QAQ

传送门

Orz ZYK

构造出数列$a_n=b\times a_{n-1}+\frac{d-b^2}{4}\times a_{n-2}\ (a_0=2,a_1=b)$

题上说$b\mod 2=1,d\mod 4=1$,所以$\frac{d-b^2}{4}$是个整数,$a_n$就可以拿矩阵乘法搞出来

上面的递推式可以拿特征方程搞成这样
$a_n=(\frac{b+\sqrt d}2)^n+(\frac{b-\sqrt d}2)^n$

$(\frac{b+\sqrt d}2)^n=a_n-(\frac{b-\sqrt d}2)^n$

答案求的即为
$\lfloor(\frac{b+\sqrt d}2)^n\rfloor=\lfloor a_n-(\frac{b-\sqrt d}2)^n\rfloor$

根据题目可知,后边这坨$-(\frac{b-\sqrt d}2)^n$仅在$b\neq \sqrt d$且$n\mod 2=1$时会对答案产生影响

所以若$b\neq \sqrt d$且$n\mod 2=1$输出$a_n-1$,否则输出$a_n$

尼玛这道题必须用qword(unsigned long long)和快速乘…否则直接爆掉…坑我一晚上…


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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
program bzoj_4002;
const mo:qword=7528443412579576937;
type matrix=array[1..2,1..2]of qword;
var a,e:matrix;
b,d,n,ans:qword;
function mul(a,b:qword):qword;
var ans:qword;
begin
ans:=0;
a:=a mod mo;
b:=b mod mo;
while b>0 do
begin
if b and 1=1 then ans:=(ans+a)mod mo;
a:=a<<1 mod mo;
b:=b>>1;
end;
exit(ans);
end;
operator *(a,b:matrix)c:matrix;
var i,j,k:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to 2 do
for j:=1 to 2 do
for k:=1 to 2 do c[i,j]:=(c[i,j]+mul(a[i,k],b[k,j]))mod mo;
end;
procedure qpower(n:qword);
var p:matrix;
begin
a[1,1]:=1;
a[1,2]:=0;
a[2,1]:=0;
a[2,2]:=1;
p:=e;
while n>0 do
begin
if n and 1=1 then a:=a*p;
p:=p*p;
n:=n>>1;
end;
end;
begin
readln(b,d,n);
if n=0 then
begin
writeln(1);
halt;
end;
e[1,1]:=b;
e[1,2]:=1;
e[2,1]:=(d-mul(b,b))div 4;
e[2,2]:=0;
qpower(n-1);
ans:=(mul(b,a[1,1])+mul(2,a[2,1]))mod mo;
if (mul(b,b)<>d)and(n and 1=0) then dec(ans);
writeln(ans);
end.