脚本宝典收集整理的这篇文章主要介绍了任意模数多项式乘法逆，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目描述

蒟蒻(TheSure)刚刚打了任意模数多项式乘法逆的板子 然后(lin4xu)扔来一个多项式(F(x)，并)让(TheSure)求出它乘法逆的(x^n)项系数对mod取模的结果 (lin4xu)知道(TheSure)很菜,所以并不想难为(TheSure)： (1.) 多项式的最高次数不会超过(10) (2.) (F(0)=1) (TheSure)当然没有学会任意模数多项式乘法逆，所以需要你来帮忙

输入格式

第一行三个整数(n,k,mod),分别表示(lin4xu)想要询问多项式的乘法逆的(x^n)项系数，多项式的最高次数，模数 接下来(k)个整数：依次表示多项式的(x^1,x^2,...,x^k)项系数。

输出格式

一行一个整数，表示给出的多项式的乘法逆的第(x^n)项系数对mod取模的结果

样例输入

3 7 1000000007 9 2 6 0 8 1 7

样例输出

999999308

数据范围与约定

令(f[i])为第(x^i)系数，对于(100%)的数据：(0leq f[i]leq mod-1)且(modleq1,000,000,007) (subtask1) ((5%))(:k=1) (subtask2) ((10%))(:k=2) (subtask3) ((20%))(:nleq114514,mod=998244353) (subtask4) ((25%))(:nleq114514) (subtask5) ((40%))(:nleq1e7)

题解

(subtask1)的分白给的，显然是个等比数列 (subtask2)的分如果你比较熟悉的话，应该是个类似斐波那契数列的东西 (subtask3)直接冲个普通多项式求逆 (subtask4)直接冲个任意模数多项式求逆 (subtask5)容易发现递推系数为给出多项式系数的相反数 具体我已经想出了一个完美的证明，可惜排版太小了，写不下。

脚本宝典总结

以上是脚本宝典为你收集整理的任意模数多项式乘法逆全部内容，希望文章能够帮你解决任意模数多项式乘法逆所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。