「BZOJ3240」[Noi2013]矩阵游戏

Description

F[1][1]=1F[1][1]=1

F[i,j]=aF[i][j1]+b(j!=1)F[i,j]=a*F[i][j-1]+b (j!=1)

F[i,1]=cF[i1][m]+d(i1)F[i,1]=c*F[i-1][m]+d (i\neq 1)

递推式中aa,bb,cc,dd都是给定的常数。
现在婷婷想知道F[n][m]F[n][m]的值是多少.

Input

一行有六个整数nn,mm,aa,bb,cc,dd。意义如题所述

Output

包含一个整数,表示F[n][m]F[n][m]除以1,000,000,0071,000,000,007的余数

Solution

矩阵乘法也是满足费马小定理的。
设矩阵从左到右转移是A1A_1,从上到下转移是A2A_2
答案是就是A1(A1A2)n1A_1(A_1A_2)^{n-1}
A1=[a0b1]A_1=\begin{bmatrix}a & 0 \\b & 1 \end{bmatrix}
A2=[c0d1]A_2=\begin{bmatrix}c & 0 \\d & 1 \end{bmatrix}
初始矩阵T=[11]T=\begin{bmatrix}1 & 1\end{bmatrix}
a=1a=1或者c=1c=1要特判,因为转移变成线性了,那么费马小定理不适用,模数要等于pp

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
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const ll p = 1000000007;
const int N = 2000100;
ll n, m ,a,b,c,d;
inline ll ksm(ll x, ll y) {
ll res = 1;
for(; y; y >>= 1, x = x * x % p)
if(y & 1) res = res * x %p;
return res;
}
char s1[N], s2[N];
ll readl(char *s, ll Mod) {
int len = strlen(s + 1);
ll res = 0;
for(int i = 1; i <= len; ++i)
res = (res * 10 + s[i] - '0') % Mod;
return res;
}
struct Matrix {
ll a[3][3];
Matrix () {memset(a,0,sizeof a);}
Matrix operator * (const Matrix b) {
Matrix c;
memset(c.a, 0, sizeof c.a);
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
for(int k = 0; k < 2; ++k)
c.a[i][j] += a[i][k] * b.a[k][j] % p;
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
c.a[i][j] %= p;
return c;
}
}t,a1,a2,res,tmp;
Matrix ksm(Matrix x, ll y) {
y %= (p - 1);
Matrix res;
for(int i =0; i < 2; ++i) res.a[i][i] = 1;
for(; y; y >>= 1, x = x * x)
if(y & 1) res = res * x;
return res;
}
int main() {
scanf("%s%s",s1 + 1, s2 +1);
a = read(), b = read(), c = read(), d = read();
if(c == 1) n = readl(s1, p);
else n = readl(s1, p - 1);
if(a == 1) m = readl(s2, p);
else m = readl(s2, p - 1);
t.a[0][0] = 1, t.a[0][1] = 1;
a1.a[0][0] = a, a1.a[1][0] = b, a1.a[1][1] = 1;
a2.a[0][0] = c, a2.a[1][0] = d, a2.a[1][1] = 1;
tmp = a1;
a1 = ksm(a1, m - 1 + p - 1);
a1 = a1 * a2;
a1 = ksm(a1, n - 1 + p - 1);
a1 = a1 * ksm(tmp, m - 1 + p - 1);
t = t * a1;
writeln(t.a[0][0]);
return 0;
}