首页 > 其他分享 >多项式板子

多项式板子

时间:2023-10-07 22:57:31浏览次数:36  
标签:int 多项式 void FFT 板子 double pi

FFT

const double pi=acos(-1.0);
int rev[N];

void FFT(complex<double> *a,int nr,int flag){
    for(int i=0;i<nr;i++){
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    }
    for(int i=1;i<nr;i<<=1){
        complex<double> wn(cos(pi/i),flag*sin(pi/i));
        for(int j=0;j<nr;j+=(i<<1)){
            complex<double> w0(1,0);
            for(int k=0;k<i;k++,w0*=wn){
                complex<double> x=a[j+k],y=w0*a[i+j+k];
                a[j+k]=x+y;
                a[i+j+k]=x-y;
            }
        }
    }
}

多项式乘法

complex<double> f[N];

void multiply(double *a,double *b,int n,int m){
    for(int i=0;i<n;i++) f[i].real(a[i]);
    for(int i=0;i<m;i++) f[i].imag(b[i]);
    int l=max((int)ceil(log2(n+m)),1),len=1<<l;
    for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
    FFT(f,len,1);
    for(int i=0;i<=len;i++) f[i]=f[i]*f[i];
    FFT(f,len,-1);
    for(int i=0;i<=n+m;i++) a[i]=f[i].imag()/2.0/len+0.5;
}

标签:int,多项式,void,FFT,板子,double,pi
From: https://www.cnblogs.com/imyhy/p/17747675.html

相关文章

  • 【学习笔记】(13) 平衡树——记住不的板子
    TreapSplay无旋Treap——fhqtreap简介就是没有旋转操作的Treap,一些性质什么的都跟Treap类似。算法介绍(1)merge(x,y)将两棵“有序”(x中元素的权值最大值小于y中元素权值最小值)的Treap合并成一棵。intch[N][2],sz[N],pri[N],val[N];//val为权值,pri为优先级,sz......
  • 多项式右复合的一些特殊情况
    下文中的“复合”默认为右复合。复合\(x+c\):展开后差卷积。复合\(e^x\):\[\suma_i(e^x)^i=\suma_i\sum_j\frac{i^j}{j!}=\sum_{j}\frac{1}{j!}\sum_i\a_ii^j\]只需计算\(\sum_i\frac{a_i}{1-ix}\),分治通分即可。复合\(\sqrt{1+x}\):对于偶数项,我们可以先复合\(\sqrt{......
  • 板子
    图论Tarjan求强连通分量intn,m,tot,top,cnt;intdfn[N],low[N];intq[N],ins[N],c[N];vector<int>eg[N],scc[N],neg[N];intcd[N];voidtarjan(intu){dfn[u]=low[u]=++tot;q[++top]=u,ins[u]=1;for(autox:eg[u]){if(!dfn[x]){......
  • 2023.9.27 Shui_Dream《一类 NPC 问题的多项式时间解法》
    给出一个字符串\(P\),\(P\)是由小写英文字母构成的。求总共有多少个不同的字符串\(Q\),使得下面两个条件同时成立:字符串\(Q\)非空。字符串连接得到\(QQ\),必须满足\(QQ\)是\(P\)的子序列。因为\(n\le100\)很小所以可以直接枚举第二次出现的首位,DP求这个点两边公......
  • 字符串哈希板子
    字符串哈希板子http://oj.daimayuan.top/course/7/problem/485单哈希#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;constintp=9999971,base=101;intn,m;chara[N],b[N];//字符串a,bintha[N],hb[N],c[N];//ha是a的哈希函数,hb是b的哈希......
  • 【模板】多项式乘法、乘法逆、除法、取模、常系数齐次线性递推
    以下代码必须开-O2#include<algorithm>#include<cassert>#include<cstdio>#include<cstring>#include<vector>usingnamespacestd;#ifdefLOCAL#definedebug(...)fprintf(stderr,##__VA_ARGS__)#else#definedebug(...)void(0)#......
  • R语言非线性方程数值分析生物降解、植物生长数据:多项式、渐近回归、负指数方程、幂函
    全文链接:https://tecdat.cn/?p=33742原文出处:拓端数据部落公众号简介在选择最佳拟合实验数据的方程时,可能需要一些经验。当我们没有文献信息时该怎么办?我们建立模型的方法通常是经验主义的。也就是说,我们观察过程,绘制数据并注意到它们遵循一定的模式。例如,我们的客户可能观察......
  • 关于三次多项式复合的一个注记
    首先根据熟知的变换,复合\(f(ax^3+bx^2+cx+d)\)的问题的困难内核在于\(f(x^3+cx)\),在域上,只要解决某个\(c\neq0\)的情况,就解决了一般的情况.取\(c=-3\),我们有\[x^3-3x=(x^3+x^{-3})\circ(x+x^{-1})^{\langle-1\rangle}.\]于是问题的难点转换成了计......
  • CF70D Professor's task 题解 & 动态凸包板子
    CF70DProfessor'stask题解前言此篇题解用的是\(Andrew\),不想看这种做法的可以绕道。题意动态凸包板子题。维护动态凸包。两种操作,加一个点或查询一个点是否在凸包内。题解首先你得会静态二维凸包。维护二维凸包的方法挺多的,比如什么\(Andrew\)算法,\(Jarvis\)算法还......
  • 可持久化非确定状态AC自动分块维护线段平衡仙人掌优化最小费用最大流预处理混合图上莫
    P8946TheLostSymbol这种类型的dp的特点就是大部分转移形如\(f(i,j)\rightarrowf(i+1,j+1)\)之类的,并且当以上转移出现时原数组被清空,这就可以用一个deque来维护,然后对于全局赋值/全局加,需要对每个位置维护一个时间戳,并记录上一次赋值/加是什么时候,以便标记下传。(貌似......