BZOJ

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.