Yaoge鸡排系列之九——好多鸡排!!!(矩阵快速幂)

描述

Yaoge买了$n$块鸡排,其中第$n$块鸡排的质量为$M(n$),同时其质量$M(n)$满足$M(n)$=$f^2(n)$

已知$f(n)=x·f(n-1)+y·f(n-2)$。其中,$f(0)=1,f(1)=1$。
Yaoge希望你能帮他算出这些鸡排的总质量对$10007$取模后的结果。

输入

第一行输入一个$T$,表示有T组测试数据$(T≤10000)$,
接下来$T$行每行输入$3$个数,$n,x,y,(2≤n,x,y≤100000000)$;

输出

输出鸡排的总质量对$10007$取模后的结果

样例输入

1
2
3
2
2 1 1
3 2 3

样例输出

1
2
5
195

提示

第一组样例,$f(1)=1,f(2)=2,M(1)=1,M(2)=4$,总和等于$5$
第二组,$f(1)=1,f(2)=5,f(3)=13,M(1)=1,M(2)=25,M(3)=169$,总和等于$195$

思路

  • $S(n)=S(n-1)+ x^2 M(n-1)+ y^2 M(n-2)+ 2xy f(n-1) f(n-2)$
  • $f(n)f(n-1)=xM(n-1)+yf(n-1)f(n-2)$
  • 于是构造出转移矩阵
    $$\begin{pmatrix}
    S(n) \\
    M(n) \\
    M(n-1) \\
    f(n)f(n-1)
    \end{pmatrix} =
    \begin{pmatrix}
    1 & x^2 & y^2 & 2xy \\
    0 & x^2 & y^2 & 2xy \\
    0 & 1 & 0 & 0 \\
    0 & x & 0 & y \\
    \end{pmatrix}
    \begin{pmatrix}
    S(n-1) \\
    M(n-1) \\
    M(n-2) \\
    f(n-1)f(n-2)
    \end{pmatrix}
    $$
  • 所以有
    $$\begin{pmatrix}
    S(n) \\
    M(n) \\
    M(n-1) \\
    f(n)f(n-1)
    \end{pmatrix} =
    \begin{pmatrix}
    1 & x^2 & y^2 & 2xy \\
    0 & x^2 & y^2 & 2xy \\
    0 & 1 & 0 & 0 \\
    0 & x & 0 & y \\
    \end{pmatrix}^{n-1}
    \begin{pmatrix}
    1 \\
    1 \\
    1 \\
    1
    \end{pmatrix}
    $$
  • 然后你懂的,矩阵快速幂就好了。

代码

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
63
64
65
66
#include <bits/stdc++.h>
#define MOD 10007
#define N 4

/*----矩阵快速幂-----*/
long long tmp[N][N];
void multi(long long a[][N], long long b[][N])
{

memset(tmp, 0, sizeof tmp);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < N; k++)
{
tmp[i][j] += (a[i][k] % MOD * b[k][j] % MOD) % MOD;
tmp[i][j] %= MOD;
}
}
}

for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
a[i][j] = tmp[i][j];
}

long long res[N][N];
void Pow(long long a[][N], long long n)
{
memset(res, 0, sizeof res);
for (int i = 0; i < N; i++) res[i][i] = 1;
// 初始单位矩阵
while (n)
{
if (n & 1)
multi(res, a);
multi(a, a);
n >>= 1;
}
}
/*----矩阵快速幂-----*/

int main()
{
int t;
long long n, x, y;
scanf("%d", &t);
while (t--)
{
scanf("%lld%lld%lld", &n, &x, &y);
if (n == 1)
printf("1\n");
else
{
long long tr[4][4] =
{{1, (x * x) % MOD, (y * y) % MOD, (2 * x * y) % MOD},
{0, (x * x) % MOD, (y * y) % MOD, (2 * x * y) % MOD},
{0, 1, 0, 0},
{0, x, 0, y}};
Pow(tr, n - 1);
printf("%lld\n", ((((res[0][0] + res[0][1])% MOD + res[0][2]) % MOD + res[0][3]) % MOD));
}
}
return 0;
}
捐助作者
0%