题解 P1397 [NOI2013]矩阵游戏

五更琉璃 · 2019-11-08 19:07:41 · 题解

很毒，很喜欢。

贡献一发数学解。

先看第一个递推式 f[i][j] = a*f[i][j - 1] + b， 用高一知识解出第一个通项公式。

设 f[i][j] + \lambda = a*(f[i][j - 1] + \lambda )

展开，移项

得 b = (a-1)* \lambda 即

同时得到一行的通项公式

所以 f[i][m] = a^{m-1} * (f[i][1] + \lambda) - \lambda

再看第二个递推式，解出列之间的通项公式。事情开始变得棘手起来。

代入解出的 f[i-1][m]，得

展开

设 f[i][1] + \mu = c * a^{m - 1}*(f[i - 1][1] + \mu)

展开，移项

得

同时得到一列的通项公式

所以 f[n][1] = (c * a ^{m - 1}) ^ {n -1}*(f[1][1] + \mu ) - \mu

最后和上面行间的通项公式结合

得到最终需要的式子

展开

然后就可以快乐的AC了

接着遇到第二个问题，数据范围实在是太大了，怎么办？

好像有一个叫欧拉的小哥哥可以帮忙

有 a ^ b \equiv a ^ {b \ mod \ \varphi(p)} (mod \ p)

通过这个公式，可以在读入 n,m 的时候一边读一边模，这样可以缩小数据范围，一个是能成功读进来，另一个是能减少程序运行时间。

所以我们用拓展欧拉定理处理通项中的幂，就可以实现数学解了。

特判很烦，要有耐心。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int p = 1e9 + 7;

int power(int a, int b, int mod) {
    int res = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)
            res = res * a % mod;
    return res;
}

char n[1000007], m[1000007];
int a, b, c, d, lambda, mu;

int newn() {
    int nn = 0;
    for (int i = 0; n[i]; ++i)
        nn = nn * 10 + (n[i] - 48), nn %= (p - 1);
    return (nn - 1 + p) % p;
}

int oldn() {
    int on = 0;
    for (int i = 0; n[i]; ++i)
        on = on * 10 + (n[i] - 48), on %= p;
    return on;
}

int newm() { // 得到 m - 1
    int nm = 0;
    for (int i = 0; m[i]; ++i) 
        nm = nm * 10 + (m[i] - 48), nm %= (p - 1);
    return (nm - 1 + p) % p;
}

int oldm() {
    int om = 0;
    for (int i = 0; m[i]; ++i)
        om = om * 10 + (m[i] - 48), om %= p;
    return om;
}

int on, om;
signed main() {
    scanf("%s", n);
    scanf("%s", m);
    scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    if (a == 1) {
        if (c == 1) {
            om = oldm(), on = oldn();
            if (on == 1) {
                int f1m = 1 + (om - 1) * b % p;
                printf("%lld\n", f1m % p);
                return 0;
            }
            int fn1 = 1 + ((om - 1) * b % p + d) % p * (on - 1) % p;
            int fnm = fn1 + (om - 1) * b % p;
            printf("%lld\n", fnm % p);
            return 0;
        }
        on = oldn();
        om = oldm();
        mu = (c * (om - 1) % p * b % p + d) % p * power(c - 1, p - 2, p) % p;
        int fn1 = power(c, on - 1, p) * (1 + mu) % p - mu;
        int fnm = fn1 + (om - 1) * b % p; fnm = (fnm + p) % p;
        printf("%lld\n", fnm);
        return 0;
    }

    lambda = (b * power(a - 1, p - 2, p)) % p;
    int nm = newm();
    int nn = newn();

    if (c == 1) {
        int am_1 = power(a, nm, p);
        int am_1n_1 = power(am_1, nn, p);
        int mu = lambda + d * power(am_1 - 1, p - 2, p) % p;
        int fn1 = am_1n_1 * (1 + mu) % p- mu;
        int fnm = am_1 * (fn1 + lambda) % p - lambda;
        printf("%lld\n", fnm);
        return 0;
    }
    on = oldn();
    int am_1 = power(a, nm, p); // a ^ (m - 1)
    int cam_1 = c * am_1 % p; // c * a ^ (m - 1)
    mu = (((cam_1 * lambda % p - c * lambda % p + p) % p + d + p) % p)
          * power((cam_1 - 1 + p) % p, p - 2, p) % p;

    int fn1 = (power(cam_1, nn, p) * (1 + mu) % p - mu + p) % p;
    int fnm = (am_1 * (fn1 + lambda) % p - lambda + p) % p;
    printf("%lld\n", fnm);
    // int ans = ((power(am_1, on, p) * power(c, nn, p) % p * (1 + mu) % p + am_1 * (lambda - mu) % p - lambda) % p + p) % p;

    return 0;
}