卷积

NC205994. 卷积

描述

牛牛为了考验你卷积的能力，出了一道简单的卷积题给你做。

定义生成函数： $F(x)=\sum_{i=1} f_ix^i$ ， $f_i=af_{i-1}+bf_{i-2}|(i>=2),f_0=0,f_1=1$

现在要你求 $\sum_{i=1} F^i(x)$ 的第n项 $\mod 998244353$ 的值。

输入描述

n a b

输出描述

一个答案一行

示例1

输入:

3 1 1

输出:

说明:

$\\F(x)=x+x^2+2x^3+...<br />\\F^2(x)=x^2+2x^3+...<br />\\F^3(x)=x^3+...<br />\\x^3这一项的系数之和为5，答案即为5<br />\\F^i(x)=(F(x))^i$

示例2

输入:

234 32 12

输出:

455012190

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 18ms, 内存消耗: 608K, 提交时间: 2020-06-06 19:04:51

#include<iostream>
#include<cstdio>
using namespace std;
int n,a,b,x,y,z;
int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(a++,n--,y=1;n--;) z=(1ll*y*a+1ll*x*b)%998244353,x=y,y=z;
	cout<<z<<'\n';
}

上一题

下一题

详情