P1707 刷题比赛

· · 题解

P1707 刷题比赛

更坏的阅读体验

前置芝士：矩阵

\texttt{Description}

给定 3 个序列 a,b,c：

a_1=b_1=c_1=1 a_2=b_2=c_2=3

计算方式：

a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1 b_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k c_{k+2}=xc_{k+1}+yc_k+a_{k+1}+b_{k+1}+z^k+k+2

其中 p,q,r,t,u,v,w,x,y,z 都为给定常数。

求 a_n,b_n,c_n，答案对 m 取模。

数据范围：

4\le n\le10^{16} 2\le m\le10^{16} 1\le p,q,r,t,u,v,w,x,y,z\le100

\texttt{Solution}

因为暴力人人都会，所以直接上正解。

每次转移的项数都很少，而 n 很大，所以自然而然地想到了矩阵加速。

不难想到 1\times11 的状态矩阵初始应该长这样子：

\begin{bmatrix} a_{k+1}&b_{k+1}&c_{k+1}&a_k&b_k&c_k&k^2&k&1&w^k&z^k \end{bmatrix}

于是 11\times11 的转移矩阵随便画一下就出来了：

\begin{bmatrix} p&1&1&1&0&0&0&0&0&0&0\\ 1&u&1&0&1&0&0&0&0&0&0\\ 1&1&x&0&0&1&0&0&0&0&0\\ q&0&0&0&0&0&0&0&0&0&0\\ 0&v&0&0&0&0&0&0&0&0&0\\ 0&0&y&0&0&0&0&0&0&0&0\\ r&0&0&0&0&0&1&0&0&0&0\\ t&0&1&0&0&0&2&1&0&0&0\\ 1&0&2&0&0&0&1&1&1&0&0\\ 0&1&0&0&0&0&0&0&0&w&0\\ 0&0&1&0&0&0&0&0&0&0&z \end{bmatrix}

接下来矩阵快速幂即可。

注意因为模数太大，所以要用龟速乘。

时间复杂度：\mathcal{O}(\log n\log m)，有个 11^3 的 常数。

\texttt{Code}

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

ll m, p, q, r, t, u, v, w, x, y, z;

struct Matrix {
    int n, m;
    ll a[15][15];

    inline Matrix () {
        memset(a, 0, sizeof(a));
    }
} base, ans;

inline ll quickMul (ll a, ll b) {
    ll res = 0;
    a %= m;
    b %= m;
    while (b) {
        if (b & 1)
            res = (res + a) % m;
        b >>= 1;
        a = (a + a) % m;
    }
    return res;
}

inline Matrix operator * (Matrix a, Matrix b) {
    Matrix res;
    res.n = a.n;
    res.m = b.m;
    for (int i = 1; i <= a.n; i++)
        for (int j = 1; j <= b.m; j++)
            for (int k = 1; k <= a.m; k++)
                res.a[i][j] = (res.a[i][j] + quickMul(a.a[i][k], b.a[k][j])) % m;
    return res;
}

inline Matrix quickPow (Matrix a, ll k) {
    Matrix res;
    res.n = res.m = a.n;
    for (int i = 1; i <= a.n; i++)
        res.a[i][i] = 1;
    while (k) {
        if (k & 1)
            res = res * a;
        k >>= 1;
        a = a * a;
    }
    return res;
}

inline void init_base () {
    base.n = base.m = 11;
    base.a[1][2] = base.a[1][3] = base.a[1][4] = base.a[2][1] = base.a[2][3] = base.a[2][5] = base.a[3][1] = base.a[3][2] = base.a[3][6] = base.a[7][7] = base.a[8][3] = base.a[8][8] = base.a[9][1] = base.a[9][7] = base.a[9][8] = base.a[9][9] = base.a[10][2] = base.a[11][3] = 1;
    base.a[8][7] = base.a[9][3] = 2;
    base.a[1][1] = p;
    base.a[2][2] = u;
    base.a[3][3] = x;
    base.a[4][1] = q;
    base.a[5][2] = v;
    base.a[6][3] = y;
    base.a[7][1] = r;
    base.a[8][1] = t;
    base.a[10][10] = w;
    base.a[11][11] = z;
}

inline void init_ans () {
    ans.n = 1;
    ans.m = 11;
    ans.a[1][1] = ans.a[1][2] = ans.a[1][3] = 3;
    ans.a[1][4] = ans.a[1][5] = ans.a[1][6] = ans.a[1][7] = ans.a[1][8] = ans.a[1][9] = 1;
    ans.a[1][10] = w;
    ans.a[1][11] = z;
}

int main () {
    ll n;
    scanf("%lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld", &n, &m, &p, &q, &r, &t, &u, &v, &w, &x, &y, &z);
    if (n < 2) {
        puts("nodgd 1");
        puts("Ciocio 1");
        puts("Nicole 1");
        return 0;
    }
    init_base();
    init_ans();
    ans = ans * quickPow(base, n - 2);
    printf("nodgd %lld\nCiocio %lld\nNicole %lld", ans.a[1][1], ans.a[1][2], ans.a[1][3]);
    return 0;
}