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

• 卷积

题目描述

给定序列 的递推公式 。

令 为序列 的生成函数，求 的第 项对 取模。

正解

最终答案 是一个等比数列求和的形式，等价于 。

现在直接多项式求逆就可以做到 了，感觉卡卡就能过。

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

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

先对 求其封闭形式。

然后求 。

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

那么很显然数列 的递推公式是 ，特别的：有 。

直接递推可以做到 ，或者用矩阵优化到 。

代码

#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;
}