题解 CF1182E 【Product Oriented Recurrence】

Sol1 · 2019-06-12 22:08:24 · 题解

第一眼：很明显地递推啊

第二眼：n \leq 10^{18}？

第三眼：很明显的矩阵加速啊

然后考场上成功地没写出来。

首先，我们在想到矩阵加速之后就可以发现，f和c一定是要分开处理的。

然后，我们发现f用乘积递推貌似不好用矩阵加速，所以我们考虑以将所有f_i表示为f_1^p·f_2^q·f_3^r的形式（注意这里已经去掉了c，最后再乘上就可以了）。

于是我开始计算和化简：

显然，当我们要从(p,q,r)推导到(p_1,q_1,r_1)(f_i=f_1^p·f_2^q·f_3^r,f_{i+1}=f_1^{p_1}·f_2^{q_1}·f_3^{r_1})时，可以找到规律：p_1=r,q_1=p+r,r_1=q+r。

易得转移矩阵1为\begin{bmatrix}0&1&0\\0&0&1\\1&1&1\end{bmatrix}，计算\begin{bmatrix}1&1&1\end{bmatrix} \times \begin{bmatrix}0&1&0\\0&0&1\\1&1&1\end{bmatrix}^{n-3}的位于(1,1)的元素就是p，位于(1,2)的元素就是q，位于(1,3)的元素就是r。

问题在于怎么处理c。

还是可以写出c的转移方程：

所以我们可以开一个5 \times 5的转移矩阵和1 \times 5的答案矩阵，设其为\begin{bmatrix}k_1&k_2&k_3&k_4&k_5\end{bmatrix}。

所以我们可以让k_1维护c_{i-1}，k_2维护c_{i-2}，k_3维护c_{i-3}，k_4维护2i，k_5维护-6。

然后我们开始填这个矩阵：初始为\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\end{bmatrix}

那么因为转移的时候，我们只需要让k_1得到这个-6就可以了，所以我们可以保持k_5=1，并让k_1乘上一个-6，于是填出2项：\begin{bmatrix}0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\0&0&0&0&0\\-6&0&0&0&1\end{bmatrix}

然后，每转移一次需要让k_4\ +2，同时因为k_5一直为1，所以我们可以直接让k_5\times 2，然后保持k_4不变就可以了。

完成了这些，会发现k_1更加好整：直接按照转移方程，把所有除-6（这项已经完成转移）的项转移到k_1即可。

下面我们要做的就是完成初始矩阵了。

显然，我们应该从i=4开始，所以我们设计的实际上是i=4时的状态。直接代入就可以了：[0,0,0,8,1]。

然后，计算答案矩阵为[0,0,0,8,1]\times\begin{bmatrix}1&1&0&0&0\\1&0&1&0&0\\1&0&0&0&0\\1&0&0&1&0\\-6&0&0&2&1\end{bmatrix}^{n-3}

最后，我们发现答案就是答案矩阵的(1,1)，设其为s。

假设我们已经获得了p,q,r,s，那么显然，答案就是f_1^p·f_2^q·f_3^r·c^s \bmod 10^9+7。

注意：我们对指数取模的时候，要模phi(10^9+7)=10^9+6。

总时间复杂度\Theta(\log N)。

附上代码：

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;

const long long mod1 = 1e9 + 7ll, mod2 = 1e9 + 6ll;
struct Matrix {
    long long a[10][10];
    int n, m;
    Matrix() {
        n = m = 0;
        memset(a, 0, sizeof(a));
    }
    //矩阵乘法
    Matrix operator * (const Matrix& b) const {
        Matrix c;
        c.n = n;
        c.m = b.m;
        for (int i = 1;i <= c.n;i++) {
            for (int j = 1;j <= c.m;j++) {
                for (int k = 1;k <= m;k++) {
                    c.a[i][j] = (c.a[i][j] + (a[i][k] * b.a[k][j]) % mod2) % mod2;
                }
            }
        }
        return c;
    }
};
long long n, f1, f2, f3, c;
//生成单位矩阵
Matrix Unit(int n) {
    Matrix mtx;
    mtx.n = n;
    mtx.m = n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            mtx.a[i][j] = (i == j);
        }
    }
    return mtx;
}
//矩阵快速幂
Matrix Power(Matrix x, long long y) {
    Matrix ans = Unit(x.n);
    while (y) {
        if (y & 1) {
            ans = ans * x;
        }
        y >>= 1;
        x = x * x;
    }
    return ans;
}
//整数快速幂
long long Power_(long long x, long long y) {
    long long ans = 1;
    while (y) {
        if (y & 1) {
            ans = (ans * x) % mod1;
        }
        y >>= 1;
        x = (x * x) % mod1;
    }
    return ans;
}

void Solve() {
//完成2个初始矩阵和2个转移矩阵
    Matrix mtx1, mtx2, mtx3, mtx4;
    mtx1.n = 1; mtx1.m = 3; mtx1.a[1][1] = mtx1.a[1][2] = mtx1.a[1][3] = 1;
    mtx2.n = 3; mtx2.m = 3; mtx2.a[1][2] = mtx2.a[2][3] = mtx2.a[3][1] = mtx2.a[3][2] = mtx2.a[3][3] = 1;
    mtx3.n = 1; mtx3.m = 5; mtx3.a[1][4] = 8; mtx3.a[1][5] = 1;
    mtx4.n = 5; mtx4.m = 5; mtx4.a[1][1] = mtx4.a[1][2] = mtx4.a[2][1] = mtx4.a[2][3] = mtx4.a[3][1] = mtx4.a[4][1] = mtx4.a[4][4] = mtx4.a[5][5] = 1;
    mtx4.a[5][1] = -6; mtx4.a[5][4] = 2;
    //利用矩阵快速幂计算p,q,r,s
    mtx1 = mtx1 * Power(mtx2, n - 4);
    mtx3 = mtx3 * Power(mtx4, n - 3);
    long long ans1 = mtx1.a[1][1], ans2 = mtx1.a[1][2], ans3 = mtx1.a[1][3], ans4 = mtx3.a[1][1];
    long long ans = 1;
    //求得最终答案
    ans = (ans * Power_(f1, ans1)) % mod1;
    ans = (ans * Power_(f2, ans2)) % mod1;
    ans = (ans * Power_(f3, ans3)) % mod1;
    ans = (ans * Power_(c, ans4)) % mod1;
    printf("%I64d", ans);
}

int main() {
    scanf("%I64d%I64d%I64d%I64d%I64d", &n, &f1, &f2, &f3, &c);
    Solve();
    return 0;
}