首页 > 其他分享 >多项式全家桶

多项式全家桶

时间：2023-07-10 18:48:09浏览次数：42  
标签：frac int 多项式 ll 全家 lim equiv mod

多项式基本运算

这个博客主要用来放一些多项式的运算的板子，大部分都来自于洛谷。

多项式乘法

NTT 求个卷积即可。


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e6 + 10, mod = 998244353, GG = 3, Gi = 332748118;
ll qmi(ll a, ll k, ll p)
{
    ll res = 1;
    while (k)
    {
        if (k & 1)
            res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}
int F[N], G[N];
int rev[N];
int n, m;
int lim = 1, len;

void NTT(int a[], int opt)
{
    for (int i = 0; i < lim; i++)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    int up = log2(lim);
    for (int dep = 1; dep <= up; dep++)
    {
        int m = 1 << dep;
        int gn;
        if(opt == 1) gn = qmi(GG, (mod - 1) / m, mod);
        else gn = qmi(Gi, (mod - 1) / m, mod);
        for (int k = 0; k < lim; k += m)
        {
            int g = 1;
            for (int j = 0; j < m / 2; j ++)
            {
                int t = (ll)g * a[j + k + m / 2] % mod;
                int u = a[j + k];
                a[j + k] = (u + t) % mod;
                a[j + k + m / 2] = (u - t + mod) % mod;
                g = (ll)g * gn % mod;
            }
        }
    }
    if (opt == -1)
    {
        int inv = qmi(lim, mod - 2, mod);
        for (int i = 0; i < lim; i ++)
            a[i] = (ll)a[i] * inv % mod;
    }
}

int main()
{
    n = read(), m = read();
    for (int i = 0; i <= n; i ++)
        F[i] = (read() + mod) % mod;
    for (int i = 0; i <= m; i ++)
        G[i] = (read() + mod) % mod;

    while (lim <= n + m)
        lim <<= 1, len ++;
    for (int i = 0; i < lim; i ++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));

    NTT(F, 1), NTT(G, 1);
    for (int i = 0; i <= lim; i ++)
        F[i] = (ll)F[i] * G[i] % mod;
    NTT(F, -1);

    for (int i = 0; i <= n + m; i ++)
        cout << F[i] % mod << ' ';

    return 0;
}

多项式求逆

原理

\[\begin{aligned}A\times B &\equiv 1\ (mod \ x^n)\\ A\times B' &\equiv 1\ (mod\ x^{\frac{n}{2}}) \\A \times (B-B')&\equiv 0 \ (mod \ x^{\frac{n}{2} }) \\(B-B')^2&\equiv 0\ (mod \ x^n) \\B^2-2BB'+B'^2&\equiv 0 \ (mod\ x^n)\\A(B^2-2BB'+B'^2 )&\equiv 0 \ (mod\ x^n) \\B-2B'+AB'^2&\equiv 0\ (mod\ x^n)\\ B&\equiv 2B'-AB'^2\ (mod\ x^n)\end{aligned} \]

代码：

（警示后人：慎用memset）

inline void mul(int a[], int b[], int to[], int lim)
{
    for(int i = (lim >> 1); i <= lim; i ++ ) X[i] = Y[i] = 0;
    for(int i = 0; i < (lim >> 1); i ++ )
        X[i] = a[i] % P, Y[i] = b[i] % P;
    NTT(X, lim, 1), NTT(Y, lim, 1);
    for(int i = 0; i < lim; i ++ ) 
        to[i] = (ll)X[i] * Y[i] % P;
    NTT(to, lim, -1);
}

ll b[2][N];
void inv(ll a[], ll to[], ll n)
{
    int cur = 0;
    b[cur][0] = qmi(a[0], P - 2, P);
    int base = 1, lim = 2, len = 1;
    calc(lim, len);
    while(base <= (n + n))
    {
        cur ^= 1;
        memset(b[cur], 0, sizeof b[cur]);
        for(int i = 0; i < base; i ++ ) b[cur][i] = b[cur ^ 1][i] * 2 % P;
        mul(b[cur ^ 1], b[cur ^ 1], b[cur ^ 1], lim);
        mul(b[cur ^ 1], a, b[cur ^ 1], lim);
        for(int i = 0; i < base; i ++ )
            b[cur][i] = (b[cur][i] - b[cur ^ 1][i] + P) % P;
        base <<= 1, lim <<= 1, len ++;
        calc(lim, len);
    }
    for(int i = 0; i < lim; i ++ ) to[i] = b[cur][i];
}

MTT（任意模数多项式乘法）

取 3 个模数跑 9 遍 NTT，最后中国剩余定理合并。

#define LOCAL
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 4e5 + 10, G1 = 998244353, G2 = 1004535809, G3 = 469762049, G = 3;
int n, m, p;
int lim = 1, len;
int rev[N];
int A[3][N], B[3][N];
int a1[N], a2[N], a3[N];
ll ans[N];

__int128 qmi(__int128 a, __int128 k, __int128 p)
{
    __int128 res = 1;
    while(k)
    {
        if(k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

__int128 inv(__int128 a, __int128 mod)
{
    return qmi(a, mod - 2, mod);
}

void NTT(int a[], int mod, int opt)
{
    for(int i = 0; i < lim; i ++ )
        if(i < rev[i])
            swap(a[i], a[rev[i]]);
    int up = log2(lim);
    for(int dep = 1; dep <= up; dep ++ )
    {
        int m = 1 << dep;
        int gn;
        if(opt == 1) gn = qmi(G, (mod - 1) / m, mod);
        else gn = qmi(qmi(G, mod - 2, mod), (mod - 1) / m, mod);
        for(int j = 0; j < lim; j += m)
        {
            int g = 1;
            for(int k = 0; k < m / 2; k ++ )
            {
                int t = (ll)a[j + k + m / 2] * g % mod;
                int u = a[j + k];
                a[j + k] = (u + t) % mod;
                a[j + k + m / 2] = ((ll)u - t + mod) % mod;
                g = (ll)gn * g % mod;
            }
        }
    }
    if(opt == -1)
    {
        int inv = qmi(lim, mod - 2, mod);
        for(int i = 0; i < lim; i ++ ) a[i] = (ll)a[i] * inv % mod;
    }
}

int main()
{
    n = read(), m = read(), p = read();
    for(int i = 0; i <= n; i ++ ) A[0][i] = read(), A[1][i] = A[2][i] = A[0][i];
    for(int i = 0; i <= m; i ++ ) B[0][i] = read(), B[1][i] = B[2][i] = B[0][i];

    while(lim <= n + m + 2) lim <<= 1, len ++;
    for(int i = 0; i < lim; i ++ )
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));

    NTT(A[0], G1, 1), NTT(B[0], G1, 1);
    for(int i = 0; i < lim; i ++ ) a1[i] = (ll)A[0][i] * B[0][i] % G1;
    NTT(a1, G1, -1);

    NTT(A[1], G2, 1), NTT(B[1], G2, 1);
    for(int i = 0; i < lim; i ++ ) a2[i] = (ll)A[1][i] * B[1][i] % G2;
    NTT(a2, G2, -1);

    NTT(A[2], G3, 1), NTT(B[2], G3, 1);
    for(int i = 0; i < lim; i ++ ) a3[i] = (ll)A[2][i] * B[2][i] % G3;
    NTT(a3, G3, -1);

    for(int i = 0; i < lim; i ++ )
    {
        __int128 M = (__int128)G1 * G2 * G3;
        ans[i] = ((__int128)a1[i] * M / G1 * inv(M / G1, G1) % M
                    + (__int128)a2[i] * M / G2 * inv(M / G2, G2) % M + 
                    (__int128)a3[i] * M / G3 * inv(M / G3, G3) % M) % M % p;
    }

    for(int i = 0; i <= n + m; i ++ ) cout << ans[i] << ' ';
    
    return 0;
}

多项式求导/积分

求导公式：

\[(\sum \limits _{i=0}^na_ix^i)'=\sum \limits _{i=0}^{n-1}a_{i+1}(i+1)x^i \]

void derivative(int a[])
{
    for(int i = 0; i < n - 1; i ++ )
        d[i] = (ll)(i + 1) * a[i + 1] % P;
    d[n - 1] = 0;
}

积分公式：

\[\int (\sum \limits _{i=0}^na_ix^i)=\sum \limits _{i=1}^{n+1}\frac{a_{i-1}}{i} x^i \]

void integral(int a[])
{
    for(int i = 1; i < n; i ++ )
        in[i] = (ll)qmi(i, P - 2, P) * a[i - 1] % P;
    in[0] = 0;
}

多项式对数函数

推导：

\[\begin{aligned} g(x)&=\ln (A(x)) \\ &=f(A(x)) \end{aligned} \]

两边同时求导，根据求导公式 \(f(g(x))'=f'(g(x))g'(x)\) 可得

\[\begin{aligned} g'(x) &=f(A(x)) \\ &=\ln (A(x))'A'(x)\\ &=\frac{A'(x)}{A(x)} \end{aligned} \]

两边再同时积分，即可得 \(g(x)=\int \frac{A'(x)}{A(x)}\)。

代码：

ll b[2][N];
void inv(ll a[], ll to[], ll n)
{
    int cur = 0;
    b[cur][0] = qmi(a[0], P - 2, P);
    int base = 1, lim = 2, len = 1;
    calc(lim, len);
    while(base <= (n + n))
    {
        cur ^= 1;
        memset(b[cur], 0, sizeof b[cur]);
        for(int i = 0; i < base; i ++ ) b[cur][i] = b[cur ^ 1][i] * 2 % P;
        mul(b[cur ^ 1], b[cur ^ 1], b[cur ^ 1], lim);
        mul(b[cur ^ 1], a, b[cur ^ 1], lim);
        for(int i = 0; i < base; i ++ )
            b[cur][i] = (b[cur][i] - b[cur ^ 1][i] + P) % P;
        base <<= 1, lim <<= 1, len ++;
        calc(lim, len);
    }
    for(int i = 0; i < lim; i ++ ) to[i] = b[cur][i];
}

void derivative(ll a[], ll to[], ll n)
{
    for(int i = 0; i < n - 1; i ++ )
        to[i] = (ll)(i + 1) * a[i + 1] % P;
    to[n - 1] = 0;
}

void integral(ll a[], ll to[], ll n)
{
    for(int i = 1; i < n; i ++ )
        to[i] = qmi(i, P - 2, P) * a[i - 1] % P;
    to[0] = 0;
}

ll inte[N], INV[N], d[N], LN[N];
void ln(ll a[], ll to[], ll n)
{
    derivative(a, d, n);
    inv(a, INV, n);
    mul(d, INV, d, n, n);
    integral(d, to, n);
}

多项式 exp

牛顿迭代法：\(x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}\)。通过牛顿迭代法，可以得到一些方程的较精确解。

在多项式中，我们也可以运用牛顿迭代法。

\[G(x)=G_0(x)-\frac{F(G_0(x))}{F'(G_0(x))} \]

迭代一次精度就会翻倍，如果 \(F(G_0(x))\equiv 0\ ( mod\ x^{\frac{n}{2} })\)，那么迭代一次会变成 \(F(G(x))\equiv 0\ ( mod\ x^{n })\)。

用牛顿迭代法求解 \(B(x)\equiv e^{A(x)}\)：

\[\begin{aligned} B(x) &\equiv e^{A(x)} \\ \ln B(x) &\equiv A(x) \\ \ln B(x) - A(x)&\equiv 0 \end{aligned} \]

令 \(F(G(x))=\ln G(x) - A(x) =0\)，利用牛顿迭代法：

\[\begin{aligned} G(x)&=G_0(x)-\frac{F(G_0(x))}{F(G_0(x))'} \\ &=G_0(x)-\frac{\ln G_0(x)-A(x)}{\frac{G_0'(x)}{G_0(x)} } \\ &=\frac{G_0(x)(1-\ln G_0(x)+A(x))}{G_0'(x)} \end{aligned} \]

时间复杂度 \(O(n\log n)\)。

PS：在这里多项式求逆我被卡了好久

ll c[N], E[N];
inline void exp(ll a[], ll b[], ll n)
{
    if(n == 1)
    {
        b[0] = 1;
        return;
    }
    exp(a, b, (n + 1) >> 1);
    ln(b, LN, n);
    int lim = 1;
    while(lim <= n + n) lim <<= 1;
    for(int i = 0; i < n; i ++ ) c[i] = ((ll)a[i] - LN[i] + P) % P;
    for(int i = n; i < lim; i ++ ) LN[i] = c[i] = 0;
    c[0] ++;
    mul(c, b, b, n, n);
    for(int i = n; i < lim; i ++ ) b[i] = 0;
}

标签：frac,int,多项式,ll,全家,lim,equiv,mod
From： https://www.cnblogs.com/crimsonawa/p/17541991.html

相关文章

  • 硬核！阿里2023版Spring全家桶进阶笔记流出，堪称Java跳槽神器
    最近小伙伴在我后台留言是这样的： 现在就这光景，不比以前，会个CRUD就有人要，即使大部分公司依然只需要做CRUD的事情......现在去面试，只会CRUD还要被吐槽： 面试造火箭，工作拧螺丝，就是现在互联网最真实的写照。很多程序员都是死磕八股文，以应对面试。这种情况无可厚非，但其实最重......
  • vue3 ref全家桶(小满zs vue3 笔记六)
    tip1:vue3无响应式数据(控制台数据已经变化,但是页面无刷新)<template><div>认识Ref全家桶</div><div>{{message}}</div><button@click="change">改变</button></template><scriptsetuplang="ts">letmessage:s......
  • AA@数域和多项式
    文章目录数域封闭运算用封闭运算描述数域多项式数域P上的多项式多项式中的相关术语多项式相等零多项式多项式之间的运算加法(减法)乘法多项式运算的次数性质运算律一元多项式环带余除法整除因式和倍式整除的常用性质相互整除整除的传递性组合式依然整除数域设Р是由一些复数组成......
  • 基于模型预测控制(mpc)的车辆换道，车辆轨迹跟踪，换道轨迹为五次多项式，matlab与carsim联
    基于模型预测控制(mpc)的车辆换道，车辆轨迹跟踪，换道轨迹为五次多项式，matlab与carsim联防控制我重新表述如下：使用模型预测控制（MPC）技术进行车辆换道和轨迹跟踪，其中换道轨迹采用五次多项式。此过程中，通过将Matlab和Carsim联合使用来实现防控制。这段话涉及到的知识点和领域范围包括：模型......
  • 一元多项式课设
    代码详见目录 一、实习任务...........................................................................................-1-1.问题描述：....................................................................................-1-2.小组分工................................
  • 多项式（Ⅱ）：进阶工业
    书接上回多项式（Ⅰ）：基础工业。这部分主要写一下进阶的一些模板。多项式求逆多项式乘法逆给定一个多项式\(F(x)\)，求出一个多项式\(G(x)\)，满足\(F(x)*G(x)\equiv1(\bmod\x^n)\)。系数对\(998244353\)取模。我们先讨论比较简单的模数是\(998244353\)这样类型的。......
  • 【Spring面试全家桶】SpringMVC处理一个请求的流程是怎样的？
    (文章目录)概念和组件在SpringMVC的请求处理流程中，有几个重要的概念和组件需要了解：DispatcherServlet：它是SpringMVC的入口，接收并处理所有的请求。DispatcherServlet负责查找处理请求的Handler、视图解析、渲染视图等工作，它的配置信息保存在Web.xml文件中。HandlerMapping......
  • 多项式模复合的几乎线性算法, 支持多元多项式在线求值的数据结构
    本文简要介绍对于有限域\(\mathbbF_q\),如何快速计算多项式模复合\(f(g(X))\bmodh(X)\),其中\(f,g,h\)均是次数不超过\(n\)的多项式.介绍的思想汇总于2022年Bhargava,Ghosh,Guo,Kumar和Umans的工作:FastMultivariateMultipointEvaluationOverAllFinit......
  • 【Spring面试全家桶】@ComponentScan你真的会用吗
    (文章目录)1.@ComponentScan介绍@ComponentScan是Spring框架提供的一种自动化扫描和加载Bean的机制。它通过指定一个或多个包路径，自动扫描这些路径下的所有类，并将被注解标记的Bean（如@Component、@Service、@Repository、@Controller等等）实例化并加入到Spring容器中。这......
  • 多项式相关
    对Alex_wei博客的抄写。复数与单位根复数跳出实数域\(\mathbb{R}\)，定义\(i^2=-1\)，即\(i=\sqrt{-1}\)，并在此基础上定义复数\(a+bi\)，其中将\(b\not=0\)的称为虚数。复数域记为\(\mathbb{C}\)。我们根据上面的定义一下复数的四则运算。加法：\((a+bi)+(c+di)=(a+c......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99