洛谷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;
}