题解P1707 刷题比赛

P1707 刷题比赛

一道显而易见的矩阵加速题，只需要将转移矩阵按照题目的要求构建出来就行了。

状态矩阵

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

转移矩阵

$$\begin{vmatrix}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\\0&1&0&0&0&0&0&0&w&0&0\\0&0&1&0&0&0&0&0&0&z&0\\1&0&2&0&0&0&1&1&0&0&1 \end{vmatrix}$$

然后直接套板子就可以了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define lll __int128
using namespace std;
typedef long long ll;

ll n, m;
struct matrix 
{
    ll dt[12][12];
    matrix operator * (const matrix b) const
    {
        matrix c;
        memset(c.dt, 0, sizeof(c.dt));
        for (int i = 1; i <= 11; i++)
            for (int j = 1; j <= 11; j++)
                for (int k = 1; k <= 11; k++)
                    c.dt[i][j] = (c.dt[i][j] + (lll)dt[i][k] * b.dt[k][j]) % m;
        return c;
    }
} a, ito;

matrix qmi(matrix base, ll b)
{
    matrix res;
    memset(res.dt, 0, sizeof(res.dt));
    for (int i = 1; i <= 11; i++)
        res.dt[i][i] = 1;
    while (b)
    {
        if (b & 1)
            res = res * base;
        base = base * base;
        b >>= 1;
    }
    return res;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    int p, q, r, t, u, v, w, x, y, z;
    scanf("%d%d%d%d%d%d%d%d%d%d", &p, &q, &r, &t, &u, &v, &w, &x, &y, &z);
    a.dt[1][1] = a.dt[1][2] = a.dt[1][3] = 3;
    a.dt[1][4] = a.dt[1][5] = a.dt[1][6] = a.dt[1][7] = a.dt[1][8] = 1;;
    a.dt[1][9] = w, a.dt[1][10] = z, a.dt[1][11] = 1;
    ito.dt[1][1] = p, ito.dt[1][2] = ito.dt[1][3] = ito.dt[1][4] = 1;
    ito.dt[2][1] = ito.dt[2][3] = ito.dt[2][5] = 1, ito.dt[2][2] = u;
    ito.dt[3][1] = ito.dt[3][2] = ito.dt[3][6] = 1, ito.dt[3][3] = x;
    ito.dt[4][1] = q, ito.dt[5][2] = v, ito.dt[6][3] = y;
    ito.dt[7][1] = r, ito.dt[7][7] = 1;
    ito.dt[8][1] = t, ito.dt[8][7] = 2, ito.dt[8][8] = ito.dt[8][3] = 1;
    ito.dt[9][2] = 1, ito.dt[9][9] = w;
    ito.dt[10][3] = 1, ito.dt[10][10] = z;
    ito.dt[11][1] = ito.dt[11][7] = ito.dt[11][8] = ito.dt[11][11] = 1, ito.dt[11][3] = 2;
    a = a * qmi(ito, n - 2);
    printf("nodgd %lld\nCiocio %lld\nNicole %lld", a.dt[1][1], a.dt[1][2], a.dt[1][3]);
    return 0;
}