【xsy2978】Product of Roots 生成函数+多项式ln+多项式exp

发布时间：2020-12-14 01:16:55 所属栏目：Linux 来源：网络整理

导读：题目大意：给你两个多项式$f(x)$和$g(x)$，满足$f(x)=prodlimits_{i=1}^{n}(a_i+1)，$g(x)=prodlimits_{i=1}^{m}(b_i+1)$。现在给你一个多项式$h(x)$，满足$h(x)=prodlimits_{i=1}^{n}prodlimits_{j=1}^{m}(a_ib_j+1)$ 请输出多项式$h$的前$k$项，

题目大意：给你两个多项式$f(x)$和$g(x)$，满足$f(x)=prodlimits_{i=1}^{n}(a_i+1)，$g(x)=prodlimits_{i=1}^{m}(b_i+1)$。

现在给你一个多项式$h(x)$，满足$h(x)=prodlimits_{i=1}^{n}prodlimits_{j=1}^{m}(a_ib_j+1)$

请输出多项式$h$的前$k$项，在模$998244353$意义下进行。

数据范围：$n,m≤10^5$。

我们现在有:

$f(x)=prodlimits_{i=1}^{n}(a_i+1)$

我们在等式两边都取对数，然后泰勒展开，得到：

$begin{align}?ln big(f(x)big) =&sumlimits_{i=1}^{n} ln(a_i+1) =&sumlimits_{i=1}^{n} sum_{k=1}^{infty} frac{(-1)^{k+1}}{k}x^ka_i^{k}end{align}$

我们不难推出：

$[x^k]ln(f(x))=sumlimits_{i=1}^{n}?frac{(-1)^{k+1}}{k}a_i^{k}$

$g(x)$同理。

我们现在来考虑$h(x)$，我们现在有：

$h(x)=prodlimits_{i=1}^{n}prodlimits_{j=1}^{m}(a_ib_j+1)$

和上面一样，我们在等式两边都取对数，然后泰勒展开，得到：

$begin{align}
lnbig(h(x)big) =&sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}ln(a_ib_j+1)
=&sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}sum_{k=1}^{infty} frac{(-1)^{k+1}}{k}x^ka_i^{k}b_j^{k}
=&sumlimits_{k=1}^{infty}x^k sumlimits_{i=1}^{n} frac{(-1)^{k+1}}{k}a_i^{k}sumlimits_{i=1}^{m} b_i^{k}
=&sumlimits_{k=1}^{infty}frac{k}{(-1)^{k+1}}x^k sumlimits_{i=1}^{n} frac{(-1)^{k+1}}{k}a_i^{k}sumlimits_{i=1}^{m} frac{(-1)^{k+1}}{k}b_i^{k}
end{align}$

我们不难推出：

$begin{align}[x^k]ln(h(x))=&frac{k}{(-1)^{k+1}} sumlimits_{i=1}^{n} frac{(-1)^{k+1}}{k}a_i^{k}sumlimits_{i=1}^{m} frac{(-1)^{k+1}}{k}b_i^{k}
=&frac{k}{(-1)^{k+1}}[x^k]lnbig(f(x)big)lnbig(g(x)big)
end{align}$

我们可以考虑，用多项式求$ln$，求出$lnbig(f(x)big)$和$lnbig(g(x)big)$，然后求出$ln(h(x))$后再用多项式$exp$算回去，就得到多项式$h$了。

套一个多项式的板子就可以了。

完结撒花

  1 #include<bits/stdc++.h>
  2 #define M (1<<19)
  3 #define L long long
  4 #define MOD 998244353
  5 #define G 3
  6 using namespace std;
  7 
  8 L pow_mod(L x,L k){
  9     L ans=1;
 10     while(k){
 11         if(k&1) ans=ans*x%MOD;
 12         x=x*x%MOD; k>>=1;
 13     }
 14     return ans;
 15 }
 16 
 17 void change(L a[],int n){
 18     for(int i=0,j=0;i<n-1;i++){
 19         if(i<j) swap(a[i],a[j]);
 20         int k=n>>1;
 21         while(j>=k) j-=k,k>>=1;
 22         j+=k;
 23     }
 24 }
 25 void NTT(L a[],int n,int on){
 26     change(a,n);
 27     for(int h=2;h<=n;h<<=1){
 28         L wn=pow_mod(G,(MOD-1)/h);
 29         for(int j=0;j<n;j+=h){
 30             L w=1;
 31             for(int k=j;k<j+(h>>1);k++){
 32                 L u=a[k],t=w*a[k+(h>>1)]%MOD;
 33                 a[k]=(u+t)%MOD;
 34                 a[k+(h>>1)]=(u-t+MOD)%MOD;
 35                 w=w*wn%MOD;
 36             }
 37         }
 38     }
 39     if(on==-1){
 40         L inv=pow_mod(n,MOD-2);
 41         for(int i=0;i<n;i++) a[i]=a[i]*inv%MOD;
 42         reverse(a+1,a+n);
 43     }
 44 }
 45 
 46 void getinv(L a[],L b[],int n){
 47     if(n==1){b[0]=pow_mod(a[0],MOD-2); return;}
 48     static L c[M],d[M];
 49     memset(c,0,n<<4); memset(d,n<<4);
 50     getinv(a,c,n>>1);
 51     for(int i=0;i<n;i++) d[i]=a[i];
 52     NTT(d,n<<1,1); NTT(c,1);
 53     for(int i=0;i<(n<<1);i++) b[i]=(2*c[i]-d[i]*c[i]%MOD*c[i]%MOD+MOD)%MOD;
 54     NTT(b,-1);
 55     for(int i=0;i<n;i++) b[n+i]=0;
 56 }
 57 
 58 void qiudao(L a[],int n){
 59     memset(b,sizeof(b));
 60     for(int i=1;i<n;i++) b[i-1]=i*a[i]%MOD;
 61 }
 62 void jifen(L a[],int n){
 63     memset(b,sizeof(b));
 64     for(int i=0;i<n;i++) b[i+1]=a[i]*pow_mod(i+1,MOD-2)%MOD;
 65 }
 66 
 67 void getln(L a[],int n){
 68     static L c[M],d[M];
 69     memset(c,n<<4);
 70     qiudao(a,n); getinv(a,d,n);
 71     NTT(c,1); NTT(d,1);
 72     for(int i=0;i<(n<<1);i++) c[i]=c[i]*d[i]%MOD;
 73     NTT(c,-1);
 74     jifen(c,b,n);
 75 }
 76 
 77 void getexp(L a[],int n){
 78     if(n==1){b[0]=1; return;}
 79     static L lnb[M]; memset(lnb,n<<4);
 80     getexp(a,n>>1); getln(b,lnb,n);
 81     for(int i=0;i<n;i++) lnb[i]=(a[i]-lnb[i]+MOD)%MOD,b[i+n]=0;
 82     lnb[n]=0;
 83     lnb[0]=(lnb[0]+1)%MOD;
 84     NTT(lnb,1); NTT(b,1);
 85     for(int i=0;i<(n<<1);i++) b[i]=b[i]*lnb[i]%MOD;
 86     NTT(b,-1);
 87     for(int i=0;i<n;i++) b[i+n]=0;
 88 }
 89 
 90 int n,m,k,len;
 91 L f[M]={0},g[M]={0},h[M]={0},lf[M]={0},lg[M]={0},lh[M]={0};
 92 
 93 int main(){
 94     scanf("%d%d%d",&n,&m,&k);
 95     for(len=1;len<=(n+m+2);len<<=1);
 96     for(int i=0;i<=n;i++) scanf("%lld",f+i);
 97     for(int i=0;i<=m;i++) scanf("%lld",g+i);
 98     getln(f,lf,len);
 99     getln(g,lg,len);
100     for(int i=0;i<len;i++) lh[i]=(lf[i]*lg[i]%MOD*(i&1?i:-i)%MOD+MOD)%MOD;
101     getexp(lh,h,len);
102     for(int i=0;i<k;i++) printf("%lld ",h[i]);
103 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!