请选择 进入手机版 | 继续访问电脑版

用多项式的逆优化dp总结

[复制链接]
命中不缺你 发表于 2021-1-3 12:07:12 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
用多项式的逆优化dp总结

思量一个经典的模子:
                                     d                                   p                            i                                  =                                   ∑                                       j                               =                               1                                      i                                  d                                   p                                       i                               −                               j                                            ×                                   f                            j                                       dp_i=\sum_{j=1}^i dp_{i-j}\times f_j                  dpi​=∑j=1i​dpi−j​×fj​
求                              d                               p                         n                                  dp_n               dpn​ 这种问题外貌看上去需要                                       n                         2                                  n^2               n2,但是事实上可以更优。
我们创建一个长度无穷大的多项式:                              F                      (                      x                      )                      =                               ∑                                   i                            =                            0                                  ∞                                       f                         i                              ×                               x                         i                                  F(x)=\sum _{i=0}^\infty f_{i}\times x^i               F(x)=∑i=0∞​fi​×xi,特殊的:                                       f                         0                              =                               f                                   k                            +                            n                                       =                      0                      ,                      k                      ∈                               N                         ∗                                  f_{0}=f_{k+n}=0,k\in \mathbb{N}^*               f0​=fk+n​=0,k∈N∗
然后可以发现                              d                               p                         n                              =                               ∑                                   i                            =                            0                                  ∞                              [                               x                         n                              ]                      (                               F                         i                              (                      x                      )                      )                          dp_n=\sum _{i=0}^{\infty}[x^n](F^i(x))               dpn​=∑i=0∞​[xn](Fi(x))
由于                                       ∑                                   i                            =                            0                                  ∞                                       x                         i                              =                               1                                   1                            −                            x                                           \sum _{i=0}^{\infty} x^i=\frac{1}{1-x}               ∑i=0∞​xi=1−x1​
所以:                              d                               p                         n                              =                      [                               x                         n                              ]                               1                                   1                            −                            F                            (                            x                            )                                           dp_{n}=[x^n]\frac{1}{1-F(x)}               dpn​=[xn]1−F(x)1​
然后                              d                               p                         n                                  dp_n               dpn​就是多项式                              G                      (                      x                      )                      =                      1                      −                      F                      (                      x                      )                          G(x)=1-F(x)               G(x)=1−F(x)的逆的第n项系数。
如何求多项式的逆元?

题解 P4238 【模板】多项式求逆- Great_Influence 的博客 - 洛谷博客 (luogu.com.cn)
my code:
[code]const int MOD=998244353;const int g=3;int len;int rev[11]>>1;                if(i&1) rev|=len>>1;         }        rep(i,len) if(rev>i) swap(v,v[rev]);}LL quick(LL A,LL B){        if(B==0) return 1;        LL  tmp=quick(A,B>>1);        tmp*=tmp;        tmp%=MOD;        if(B&1)                tmp*=A,tmp%=MOD;         return tmp;}int inv(int x){        return quick(x,MOD-2);}vector ntt(vector v,int ty){        butterfly(v);        vector nex;        for(int l=2;l
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )