题目大意
求 $(3+\sqrt 5)^n$ 的整数部分最后三位。
$n \le 2 \times 10^9$
这真是个有趣的问题
解法
考虑一项一项地乘
某个数 $a+b\sqrt 5$，给它乘个 $3+\sqrt 5$ 之后，会变成 $(3a+5b)+(a+3b)\sqrt 5$。
于是可以考虑矩阵乘法。
但是直接这样矩阵乘法不能模！！！
原因是，$a=a\bmod 1000$，但 $b\sqrt 5≠(b \bmod 1000)\sqrt 5$
所以再考虑 $(3-\sqrt 5)^n$。设 $(3+\sqrt 5)^n=a+b\sqrt 5$，那么 $(3-\sqrt 5)^n$ 就等于 $a-b\sqrt 5$。两式相加得 $2a$。
又由于 $0<3-\sqrt 5<1$，所以 $0<(3-\sqrt 5)^n<1$，因此答案就是 $2a-1$。
于是我们矩阵乘法只需要求 $a$，这样就可以模了！！
（个人感觉妙啊。。。）