BZOJ3240【NOI2013】矩阵游戏 <欧拉定理>

Problem

【NOI2013】矩阵游戏

Description

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的行列的矩阵(你不用担心她如何存储)。
她生成的这个矩阵满足一个神奇的性质：若用来表示矩阵中第行第列的元素，则满足下面的递推式:

递推式中都是给定的常数。
现在婷婷想知道的值是多少，请你帮助她。
由于最终结果可能很大，你只需要输出除以的余数。

Input

一行有六个整数。

Output

包含一个整数，表示除以的余数。

Sample Input

3 4 1 3 2 6

Sample Output

85

HINT

样例中的矩阵为：

标签：欧拉定理

Solution

先推横向，从推到：

然后就有纵向的递推式：

将的参数作为常数，后面也作为常数，令，，。
再次做和上面相同的化简，得

而，即可求解。

由于很大，需要用欧拉定理，即，其中是质数。注意读入时需要处理和的值，因为同时会在上标和底数中出现。

Code

#include <bits/stdc++.h>
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
template <class T> inline void read_sup(T &x, T &y) {
    x = y = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar())
        x = (x*10+f*(c-'0'))%P, y = (y*10+f*(c-'0'))%(P-1);
}
lnt n0, n1, m0, m1, a, b, c, d, x, y, z, f;
lnt Pow(lnt x, lnt k) {
    lnt ret = 1; if (k < 0) k += (P-1);
    for (; k; k >>= 1, x = x*x%P)
        if (k&1) ret = ret*x%P;
    return ret;
}
lnt Inv(lnt x) {return Pow(x, P-2);}
int main() {
    read_sup(n0, n1), read_sup(m0, m1);
    read(a), read(b), read(c), read(d);
    x = Pow(a, m1-1)*c%P, z = ((P+m0-1)%P*b%P*c%P+d)%P;
    y = ((Pow(a, m1-1)+P-1)%P*b%P*c%P*Inv(a-1)%P+d)%P;
    if (a == 1 && c == 1) f = (1+z*n0%P)%P;
    else if (a == 1 && c > 1)
        f = (Pow(c, n1)+(Pow(c, n1)+P-1)%P*Inv(c-1)%P*z%P)%P;
    else f = (Pow(x, n1)+(Pow(x, n1)+P-1)%P*Inv(x-1)%P*y%P)%P;
    f = (f+P-d)%P*Inv(c)%P; return printf("%lld\n", f), 0;
}