题解-P5137

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

计算 $(\sum\limits_{i=0}^na^ib^{n-i})\bmod p$ 的值。

解题思路

式子题。

我们定义 $f_i = \sum\limits_{j=0}^ia^jb^{i-j}$，然后我们尝试推出一个递推式。

而这个递推式我们可以使用矩阵乘法进行加速。

具体地说，定义我们的状态矩阵为 $\begin{bmatrix}f_i \\ a^i\end{bmatrix}$，那么应该转移成 $\begin{bmatrix}bf_i+a^{i+1} \\ a^{i+1}\end{bmatrix}$，中间乘的矩阵为 $\begin{bmatrix}b & a \\ 0 & a\end{bmatrix}$。

答案就应该是 $(\begin{bmatrix}b & a \\ 0 & a\end{bmatrix})^n\begin{bmatrix}1 \\ 1\end{bmatrix}$（注意顺序哦）。

因为这道题的特殊性（略卡常），我就给出完整代码供参考。

#include <stdio.h>
#include <string.h>
#include <ctype.h>

typedef unsigned long long i64;
typedef __int128 i128;

inline i64 read()
{
    char c = getchar();
    i64 x = 0;
    for (; !isdigit(c); c = getchar())
        ;
    for (; isdigit(c); c = getchar())
        x = (x * 10) + (c - '0');
    return x;
}

inline void print(i64 x)
{
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}

struct matrix
{
    i64 c[4];
    matrix()
    {
        c[0] = c[1] = c[2] = c[3] = 0;
    }
};

i64 mod = -1, T, n, a, b, c, d;

#define pos00 .c[0]
#define pos01 .c[1]
#define pos10 .c[2]
#define pos11 .c[3]

inline matrix mutl(matrix a, matrix b)
{
    matrix res;
    res pos00 = (i128(a pos00) * b pos00 + i128(a pos01) * b pos10) % mod;
    res pos01 = (i128(a pos00) * b pos01 + i128(a pos01) * b pos11) % mod;
    res pos10 = (i128(a pos10) * b pos00 + i128(a pos11) * b pos10) % mod;
    res pos11 = (i128(a pos10) * b pos01 + i128(a pos11) * b pos11) % mod;
    return res;
}
matrix bm2, intl, A;

matrix fastpow(matrix num, i64 p)
{
    matrix res = bm2;
    while (p)
    {
        if (p & 1)
            res = mutl(res, num);
        num = mutl(num, num);
        p >>= 1;
    }
    return res;
}

int main()
{
    intl pos00 = 1;
    intl pos10 = 1;
    bm2 pos00 = 1;
    bm2 pos11 = 1;

    T = read();

    while (T--)
    {
        n = read();
        a = read();
        b = read();
        mod = read();

        A pos00 = b;
        A pos01 = a;
        A pos10 = 0;
        A pos11 = a;

        A = mutl(fastpow(A, n), intl);

        print(A pos00);
        putchar('\n');
    }
}