题目描述

给定序列 的递推公式

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

正解

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

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

比赛的时候不会生成函数真的自闭了啊,然后想起了 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;
}