洛谷P1707 刷题比赛题解

题意：

洛谷OJ当然算是好地方，nodgd 同学打算和朋友分享一下。于是他就拉上了他的朋友 Ciocio 和 Nicole 两位同学一起刷题。喜欢比赛的他们当然不放过这样一次刷题比赛的机会！

在第 $1$ 天 nodgd,Coicoi,Nicole 都只做了 $1$ 道题。

在第 $2$ 天 nodgd,Coicoi,Nicole 都只做了 $3$ 道题。

他们都有着严格的刷题规则，并且会在每一天都很遵守规则的刷一定量的题。

nodgd 同学第 $k+2$ 天刷题数量
$a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1$

Ciocio 同学第 $k+2$ 天刷题数量
$b_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k$

Nicole 同学第 $k+2$ 天刷题数量
$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$ 都是给定的常数，并保证是正整数）

于是他们开始了长时间的刷题比赛！一共进行了 $n$ 天。

但是时间是可贵的，nodgd 想快速知道第 $n$ 天每个人的刷题数量。

不过 nodgd 同学还有大量的数学竞赛题、物理竞赛题、英语竞赛题、美术竞赛题、体育竞赛题…… 要做，就拜托你来帮他算算了。

由于结果很大，输出结果 $\bmod \space m$ 的值即可。

输入格式：

第一行两个正整数 $n,m$。

第二行四个正整数 $p,q,r,t$。

第三行三个正整数 $u,v,w$。

第四行三个正整数 $x,y,z$。

输出格式：

共三行，每行一个名字 + 一个空格 + 一个整数。

依次是 nodgd,Ciocio,Nicole 和他们在第 $n$ 天刷题数量 $\bmod \space m$ 的值。

数据范围：

$4\le n \le 10^{16},~2\le m \le 10^{16},~1\le p,q,r,t,u,v,w,x,y,z \le 100$。

我一看，啊，又是大模数，又是离谱大的矩阵快速幂，纯属搞人心态的。

不急，我们一个个来看。首先可以发现里面有些简单的，例如 $pa_{k+1}$ 这种，直接加进初始矩阵就好。

然后就是 $w^k,z^k$ 这种。我们可以直接在矩阵里面 $w^k \times w = w^{k+1}$ 。

可能最难的就是 $k^2$ 了吧，其实也不难，因为有 $(k + 1) ^ 2 = k^2 + 2k + 1$ ，所以只要稍微弄下就好了

考虑构建递推矩阵：（初始矩阵为 $k=1$ 时）

$A = \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}$

转移矩阵如下：

$M = \left[\begin{array}{lllllllllll} 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{array}\right]$

我们只需要求一下 $A \times M^{n-1}$ 就好啦，别忘了这个模数太大需要用 __int128 优化哦~

时间复杂度 $\mathcal{O}(11^3\times \log n)$

代码：（~~最优解 34ms 可以吹一下的~~）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef vector< vector<int> > mat;
int mod;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : x; }
#define N ((int)())

int qpow(int a,int b)
{
    int ans = 1; for(; b; b >>= 1)
    {
        if(b & 1) ans = (__int128)ans * a % mod;
        a = (__int128)a * a % mod;
    }
    return ans;
}
mat mul(mat A, mat B)
{
    int n = A.size(), m = A[0].size(), p = B[0].size();
    mat C(n, vector<int>(p));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < p; j++)
        {
            __int128 t = 0;
            for(int k = 0; k < m; k++) t += (__int128)A[i][k] * B[k][j];
            add(C[i][j], t % mod);
        }
    return C;
}
mat qpow(mat A, int b)
{
    int n = max(A.size(), A[0].size());
    mat ans(n, vector<int>(n));
    for(int i = 0; i < n; i++) ans[i][i] = 1;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = mul(ans, A);
        A = mul(A, A);
    }
    return ans;
}
mat M(11, vector<int>(11)), A(1,vector<int>(11));
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,p,q,r,t,u,v,w,x,y,z; cin >> n >> mod; 
    cin >> p >> q >> r >> t >> u >> v >> w >> x >> y >> z;
    A[0][0] = A[0][1] = A[0][2] = 3; A[0][3] = A[0][4] = A[0][5] = 1;
    A[0][6] = A[0][7] = A[0][8] = 1; A[0][9] = w; A[0][10] = z;
    M[0][0] = p; M[0][1] = 1; M[0][2] = 1; M[0][3] = 1;
    M[1][0] = 1; M[1][1] = u; M[1][2] = 1; M[1][4] = 1;
    M[2][0] = 1; M[2][1] = 1; M[2][2] = x; M[2][5] = 1;
    M[3][0] = q;
    M[4][1] = v;
    M[5][2] = y;
    M[6][0] = r; M[6][6] = 1;
    M[7][0] = t; M[7][2] = 1; M[7][6] = 2; M[7][7] = 1;
    M[8][0] = 1; M[8][2] = 2; M[8][6] = 1; M[8][7] = 1; M[8][8] = 1; 
    M[9][1] = 1; M[9][9] = w;
    M[10][2] = 1; M[10][10] = z;
    mat res = mul(A, qpow(M, n - 1));
    cout << "nodgd " << res[0][3] << '\n';
    cout << "Ciocio " << res[0][4] << '\n';
    cout << "Nicole " << res[0][5] << '\n';
    return 0;
}