P4451 [国家集训队]整数的lqp拆分

P4451 [国家集训队]整数的lqp拆分

先考虑 $F$ 的生成函数。因为有 $[x ^ i]F(x) = [x ^ {i - 1}] F(x) + [x ^ {i - 2}] F(x)$ ，即 $F(x) = (xF(x) + f(0)) + (x ^ 2F(x) + f(1)x + f(0))$ ，即 $F(x) = \frac x {1 - x - x ^ 2}$ 。那么对于 $m$ 个数，答案为 $[x ^ n] F(x) ^ m$ 。故答案为 $\sum _ {i = 0} [x ^ n] F(x) ^ i = [x ^ n] \sum _ {i = 0} F(x) = [x ^ n] \frac 1 {1 - F(x)} = \frac {1 - x - x ^ 2}{1 - 2x - x ^ 2}$ 。考虑分母 $G(x) = \frac 1 {1 - 2x - x ^ 2}$ 对应的递推公式，整理得 $G(x) = 2xG(x) + x ^ 2G(x) + 1$ ，那么有 $g(x) = 2g(x - 1) + g(x - 2)$ 。再考虑分子，答案为 $g(n) - g(n - 1) - g(n - 2) = g(n - 1)$ 。手算 $g(1) = 1, g(2) = 2$ ，矩阵快速幂即可。

查看代码

#include <cstdio>
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7;
const int N = 3;
template <class Type>
void op (Type &x, Type &a, Type &b) { (x += (LL)a * b % mod) %= mod; }
template <class Type>
struct Matrix
{
    int n, m;
    Type w[N][N];
    Matrix() { }
    Matrix(int x, int y) { n = x, m = y; }
    Matrix(int x, int y, Type k)
    {
        n = x, m = y;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                w[i][j] = i == j ? k : 0;
    }
    friend Matrix operator*(Matrix x, Matrix y)
    {
        Matrix res(x.n, y.m, Type(0));
        for (int i = 1; i <= res.n; i++)
            for (int j = 1; j <= res.m; j++)
                for (int k = 1; k <= x.m; k++)
                    op(res.w[i][j], x.w[i][k], y.w[k][j]);
        return res;
    }
    friend Matrix operator^(Matrix b, int k)
    {
        Matrix res(b.n, b.m, Type(1));
        for (; k; k >>= 1, b = b * b)
            if (k & 1) res = res * b;
        return res;
    }
};
int main ()
{
    char c;
    while ((c = getchar()) < '0' || c > '9') c = getchar();
    int n = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        n = (10ll * n + c - '0') % (mod - 1);
    Matrix <int> A(1, 2), B(2, 2);
    A.w[1][1] = 1, A.w[1][2] = 2;
    B.w[1][1] = 0, B.w[1][2] = 1, B.w[2][1] = 1, B.w[2][2] = 2;
    printf("%d", (A * (B ^ n - 1)).w[1][1]);
    return 0;
}