class="markdown_views prism-github-gist"> 题目描述 给定一个多项式F(x)" role="presentation" style="position: relative;">F(x)$F(x)$，请求出一个多项式G(x)" role="presentation" style="position: relative;">G(x)$G(x)$，满足F(x)∗G(x)≡1(mod xn)" role="presentation" style="position: relative;">F(x)∗G(x)≡1(mod xn)$F(x)\ast G(x)\equiv 1(mod{x}^n)$。系数对109+7" role="presentation" style="position: relative;">109+7${10}^9+7$取模。 输入输出格式 输入格式：
首先输入一个整数n" role="presentation" style="position: relative;">n$n$，表示输入多项式的次数。
接着输入n" role="presentation" style="position: relative;">n$n$个整数，第i" role="presentation" style="position: relative;">i$i$个整数ai" role="presentation" style="position: relative;">ai$a_i$，代表F(x)" role="presentation" style="position: relative;">F(x)$F(x)$次数为i−1" role="presentation" style="position: relative;">i−1$i-1$的项的系数。 输出格式：
输出n" role="presentation" style="position: relative;">n$n$个数字，第i" role="presentation" style="position: relative;">i$i$个整数bi" role="presentation" style="position: relative;">bi$b_i$，代表G(x)" role="presentation" style="position: relative;">G(x)$G(x)$次数为i−1" role="presentation" style="position: relative;">i−1$i-1$的项的系数。 输入输出样例 输入样例#1：
5
1 6 3 4 9
输出样例#1：
1 998244347 33 998244169 1020
说明
1≤n≤105,0≤ai≤109" role="presentation" style="position: relative;">1≤n≤105,0≤ai≤109$1\le n\le {10}^5,0\le a_i\le {10}^9$ 分析：
这题就用来复习多项式求逆和任意模。
还是直接结论，设A(x)" role="presentation" style="position: relative;">A(x)$A(x)$为原多项式，B(x)" role="presentation" style="position: relative;">B(x)$B(x)$为在xn" role="presentation" style="position: relative;">xn$x^n$意义下的逆元，B′(x)" role="presentation" style="position: relative;">B′(x)$B^{\prime }(x)$为在xn2" role="presentation" style="position: relative;">xn2$x^{\frac{n}{2}}$的逆元，有
B(x)≡2B′(x)−A(x)B′(x)2" role="presentation" style="text-align: center; position: relative;">B(x)≡2B′(x)−A(x)B′(x)2$$B(x)\equiv 2B^{\prime }(x)-A(x)B^{\prime }(x{)}^2$$
因为模数是109+7" role="presentation" style="position: relative;">109+7${10}^9+7$，肯定是不能ntt" role="presentation" style="position: relative;">ntt$ntt$的。像我这种习惯打任意模的丝毫没有影响，因为任意模是2" role="presentation" style="position: relative;">2$2$次DFT" role="presentation" style="position: relative;">DFT$DFT$和2" role="presentation" style="position: relative;">2$2$次IDFT" role="presentation" style="position: relative;">IDFT$IDFT$，而ntt" role="presentation" style="position: relative;">ntt$ntt$是2" role="presentation" style="position: relative;">2$2$次DFT" role="presentation" style="position: relative;">DFT$DFT$和1" role="presentation" style="position: relative;">1$1$次IDFT" role="presentation" style="position: relative;">IDFT$IDFT$，不会慢多少。 代码： // luogu-judger-enable-o2 #include #include #include #define LL long long const int maxn=3e5+7; const double pi=acos(-1); const LL mod=1e9+7; using namespace std; int n,len,r[maxn]; LL f[maxn],g[maxn],c[maxn]; struct rec{ double x,y; }a[maxn],b[maxn],w[maxn],dfna[maxn],dfnb[maxn],dfnc[maxn],dfnd[maxn]; rec operator +(rec a,rec b) { return (rec){a.x+b.x,a.y+b.y}; } rec operator -(rec a,rec b) { return (rec){a.x-b.x,a.y-b.y}; } rec operator *(rec a,rec b) { return (rec){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x}; } rec operator !(rec a) { return (rec){a.x,-a.y}; } void fft(rec *a,int f) { for (int i=0;iif (i0]=(rec){1,0}; for (int i=2;i<=len;i*=2) { rec wn=(rec){cos(2*pi/i),f*sin(2*pi/i)}; for (int j=i/2;j>=0;j-=2) w[j]=w[j/2]; for (int j=1;j2;j+=2) w[j]=w[j-1]*wn; for (int j=0;jfor (int k=0;k2;k++) { rec u=a[j+k],v=w[k]*a[j+k+i/2]; a[j+k]=u+v; a[j+k+i/2]=u-v; } } } } void FFT(LL *x,LL *y,LL *z,LL n,LL m) { len=1; while (len<=n+<