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

【学习笔记】多项式对数(多项式求导 + 积分)

[复制链接]
卓小兔 发表于 2021-1-2 19:42:34 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
整理的算法模板合集: ACM模板
  
目次



点我看多项式全家桶(●^                                                             ◡                                            _◡                     ◡​^●)
多项式对数

实在非常简单,就是直接求导再积分即可。

P4725 【模板】多项式对数函数(多项式 ln)


直接简单实现一下就行了。
我们输入多项式                               f                          f               f ,先求                              f                          f               f的导数                               A                          A               A ,                              f                          f               f 的逆元                               B                          B               B,然后把他们乘起来(                              N                      T                      T                          NTT               NTT),最后求积分                               g                          g               g 既是答案,输出即可。
至于求导和积分,因为我们的多项式                              f                      (                      x                      )                      =                               a                         0                              +                               a                         1                              ×                      x                      +                               a                         2                              ×                               x                         2                              …                               a                         n                              ×                               x                                   n                            −                            1                                           f(x) = a_0 + a_1 \times x + a_2 \times x^2 \dots a_n \times x^{n - 1}               f(x)=a0​+a1​×x+a2​×x2…an​×xn−1
                                    (                                   x                            a                                            )                            ′                                  =                         a                                   x                                       a                               −                               1                                                                      ,                                                   ∫                                   x                            a                                  d                         x                         =                                   1                                       a                               +                               1                                                      x                                       a                               +                               1                                                 (x^{a})'=ax^{a-1}\ ,\ \int x^adx=\frac{1}{a+1}x^{a+1}                  (xa)′=axa−1 , ∫xadx=a+11​xa+1
直接                               f                      o                      r                          for               for 循环实现以下就行了
[code]const int N = 5000007;const int p = 998244353, gg = 3, ig = 332738118;const int mod = 998244353;int limit = 1;int L;int R[N];ll f[N], g[N];ll A[N], B[N], C[N];template void read(T &x){    x = 0;    register int f = 1;    register char ch = getchar();    while(ch < &#39;0&#39; || ch > &#39;9&#39;) {if(ch == &#39;-&#39;)f = -1;ch = getchar();}    while(ch >= &#39;0&#39; && ch >= 1;    }    return res % p;}ll inv(ll x) {return qpow(x, mod - 2);}void NTT(ll *A, int type){    for(int i = 0; i < limit; ++ i)        if(i < R)            swap(A, A[R]);    for(int mid = 1; mid < limit; mid > 1) : 0);        C = (i < deg ? A : 0);    }    NTT(C, 1), NTT(B, 1);    for(int i = 0; i < limit; ++ i)        B = (2ll - C * B % mod + mod) % mod * B % mod;    NTT(B, -1);    fill(B + deg, B + limit, 0);}//多项式求导void get_dev(ll *A, ll *B, int n){    for(int i = 1; i < n; ++ i)        B[i - 1] = i * A % mod;    B[n - 1] = 0;}//多项式求积分void get_indev(ll *A, ll *B, int n){    for(int i = 1; i < n; ++ i)        B = A[i - 1] * qpow(i, mod - 2) % mod;    B[0] = 0;}void get_ln(ll *f, ll *g, int n){    get_dev(f, A, n);    get_inv(f, B, n);    for(limit = 1, L = 0; limit > 1) | ((i & 1)
回复

使用道具 举报

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

本版积分规则


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

18768367769

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

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

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