题解 [牛客IOI周赛17-提高组 B] 卷积

卷积

题目描述

给定序列 $f$ 的递推公式 $f_n = af_{n - 1} + bf_{n - 2} | (n \ge 2),~ f_0 = 0,~ f_1 = 1$ 。

令 $F$ 为序列 $f$ 的生成函数，求 $\sum_{i = 1}^{\infty}F^i$ 的第 $n$ 项对 $998'244'353$ 取模。

正解

最终答案 $G = \sum_{i = 1}^{\infty} F^i$ 是一个等比数列求和的形式，等价于 $G = \frac {F} {1 - F}$ 。

现在直接多项式求逆就可以做到 $O(n \log n)$ 了，~~感觉卡卡就能过~~。

比赛的时候不会生成函数真的自闭了啊，然后想起了 rqy 博客里求通项 / 递推公式的方法，尝试自己推了一下。

先对 $F$ 求出其封闭形式，然后如果 $G$ 也能表示成一个类似于生成函数封闭形式的玩意，就能求出 $G$ 的递推式。

先对 $F$ 求其封闭形式。

$\begin{aligned} \kern{100px} F &= ax \times F + bx^2 \times F + x \\ F &= \frac{x} {1 - ax - bx^2} \end{aligned}$

然后求 $G$ 。

$\begin{aligned} \kern{100px} G &= \frac {F} {1 - F} \\ G &= \frac {\frac {x} {1 - ax - bx^2}} {\frac {1 - ax - bx^2 - x} {1 - ax - bx^2}} \\ G &= \frac{x} {1 - (a + 1)x - bx^2} \end{aligned}$

发现 $G$ 与 $F$ 的封闭形式类似，应该可以求出其递推公式。

$\begin{aligned} \kern{100px} G &= \frac{x} {1 - (a + 1)x - bx^2} \\ G &= (a + 1)x \times G + bx^2 \times G + x \end{aligned}$

那么很显然数列 $g$ 的递推公式是 $g_n = (a + 1)g_{n - 1} + bg_{n - 2}$ ，特别的：有 $g_0 = 0,~ g_1 = 1$ 。

直接递推可以做到 $O(n)$ ，或者用矩阵优化到 $O(\log n)$ 。

代码

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

int n, a, b;

struct matrix {
    long long c[2][2];
    inline matrix () { c[0][0] = c[0][1] = c[1][0] = c[1][1] = 0; }
} ;

matrix mul(const matrix &A, const matrix &B) {
    matrix C;
    for(int i = 0; i < 2; ++i)
        for(int j = 0; j < 2; ++j)
            for(int k = 0; k < 2; ++k)
                C.c[i][j] += A.c[i][k] * B.c[k][j];
    C.c[0][0] %= mod;
    C.c[0][1] %= mod;
    C.c[1][0] %= mod;
    C.c[1][1] %= mod;
    return C;
}

int main() {
    scanf("%d %d %d", &n, &a, &b);
    /* g_n = (a + 1) * g_{n - 1} + b * g_{n - 2} */
    matrix base, res;
    res.c[0][0] = res.c[1][1] = 1;
    base.c[0][0] = (a + 1) % mod;
    base.c[1][0] = b;
    base.c[0][1] = 1;
    base.c[1][1] = 0;
    while(n) {
        if(n & 1) res = mul(res, base);
        base = mul(base, base), n >>= 1;
    }
    printf("%lld\n", res.c[0][1]);
    return 0;
}