牛客IOI周赛17-提高组卷积生成函数多项式求逆数列通项公式

LINK：卷积

思考的时候非常的片面导致这道题没有推出来。

虽然想到了设生成函数 G(x)表示最后的答案的普通型生成函数不过忘了化简 GG.

容易推出 \(G(x)=\frac{F(x)}{1-F(x)}\)

多项式求逆一下再卷积一下即可。(nlogn).

有dalao 提出了求通项公式的做法对多项式求出类似于泰勒展开式那样的封闭形式.

然后带入G进行化简最终再由通项公式推出来。推出通项可以可以递推可以矩阵乘法优化 O(n)/(logn).

做法来自@Lskkkno1 ：

很妙的求通项的方法不过我不太熟悉这方面的知识. 还需要多加理解！

const ll MAXN=2000010,GG=3;

ll n,a,b;

ll f[MAXN];

signed main()

{

	//freopen("1.in","r",stdin);

	get(n);get(a);get(b);

	f[1]=1;

	rep(2,n,i)f[i]=((a+1)*f[i-1]+b*f[i-2])%mod;

	putl(f[n]);return 0;

}

巴特西

牛客IOI周赛17-提高组卷积生成函数多项式求逆数列通项公式

最新文章

热门文章

巴特西

牛客IOI周赛17-提高组 卷积 生成函数 多项式求逆 数列通项公式

最新文章

热门文章

牛客IOI周赛17-提高组卷积生成函数多项式求逆数列通项公式