模板

模板

文章目录

​​素数筛​​​​欧几里得​​​​逆元​​​​卡特兰数​​​​线性基​​

​​维护每个点往左的线性基​​

​​汇总​​

素数筛

int pri[N+9>>1],now;bool vis[N+9];void init(){ for(int i=2;i<=N;i++){ if(!vis[i])pri[++now]=i; for(int j=1;j<=now&&pri[j]*i<=N;j++){ vis[pri[j]*i]=1; if(i%pri[j]==0)break; } }}

欧几里得

LL Ex_gcd(LL a,LL b,LL &x,LL &y){ if(!b){ y=0,x=1; return a; } LL ans=Ex_gcd(b,a%b,y,x); y-=a/b*x; return ans;}LL MinNotNeg(LL a,LL b,LL c){ if(!a&&!b){ return -(c!=0); } LL x,y; LL G=Ex_gcd(a,b,x,y); if(c%G)return -1; x*=c/G; y*=c/G; b=abs(b/G); return (x%b+b)%b;}int main(){ cout<

逆元

线性求解：inv [ i ] = ( m - m / i ) * inv [ m % i ]% m阶乘逆元：inv_fac[n]=swift(fac[n],mod-2); //快速幂for(int i=n-1;i>=0;i--) inv_fac[i]=(inv_fac[i+1]*(i+1))%mod;

卡特兰数

1.n个数进栈，有h(n)种出栈方式； 2.凸n边形，用多条不相交的对角线分成三角形，有h(n-2)种可能性； 3.n个节点，有h(n)种不同的二叉搜索树 4.给n对括号排序，有h(n)种不同的正确的排序方式 5.买票找零n个50元，m个100元（一开始柜台没零钱） 6.n*n棋盘从左下角走到右上角而不穿过主对角线的走法 7.矩阵连乘的括号化 8.在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数 9.n层阶梯矩阵切割成n个长度递增矩阵的切割法递推关系： h(n)=h(n-1)*(4*n-2)/(n+1);通项公式： h(n)=C(2n,n)/(n+1) (n=0,1,2,...) h(n)=C(2n,n)-C(2n,n-1)(n=0,1,2,...)进出不同： h(n,m)=C(n+m,n)-C(n+m,n+1) （n代表必须先有的项数量，n>m，如左括号，入栈）

线性基

struct linear_Bace;typedef linear_Bace LB;const int maxn=50000+9;const int Len=33;struct linear_Bace{ int a[Len]; int& operator [](int idx){ return a[idx]; } int operator [](int idx)const{ return a[idx]; } void insert(int val){ for(int i=Len-1;i>=0;i--){ if((val>>i)&1){ if(!a[i]){ a[i]=val;break; } val^=a[i]; } } } bool find(int val){ for(int i=Len-1;i>=0;i--){ if((val>>i)&1){ if(a[i]){ val^=a[i]; } else return 0; } } return 1; }};LB merge(LB a,LB b){ LB ans=a; for(int i=Len-1;i>=0;i--){ if(b[i]==0)continue; ans.insert(b[i]); } return ans;}LB intersect(LB a,LB b){ LB ans= {},c=b,d=b; for(int i=0;i=0; --j){ if((x>>j)&1) if(c[j]) { x^=c[j]; T^=d[j]; } else break; } if(!x) ans[i]=T; else { c[j]=x; d[j]=T; } } return ans;}

维护每个点往左的线性基

int ji[maxn][31];int pos[maxn][31];void deal(int n,int val){ int nex=n; rep(i,0,30)ji[n][i]=ji[n-1][i],pos[n][i]=pos[n-1][i]; rrep(i,30,0){ if(val&(1<

汇总

const F pi=acos(-1);const LL mod=1e9+7;const F _e=2.718281828459045;快速幂LL swift(LL a,LL b){ LL ans=1ll; while(b){ if(b%2)ans=ans*a%mod; b>>=1; a=a*a%mod; }return ans;}LL inv(LL a){return swift(a,mod-2);}//费马小定理扩展欧几里得int exgcd(int a, int b, int &x, int &y){ if(b==0){x=1;y=0;return a;} int r=exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y;return r; //int a=11,b=35,x,y,c=4; //int ans=exgcd(a,b,x,y); //printf("%d * %d + %d * %d = %d\n",a,c/ans*x,b,c/ans*y,c);}无取模求gcdLL stein(LL a, LL b){ if(a==0) return b; if(b==0) return a; if(a%2==0&&b%2==0) return 2*stein(a>>1,b>>1); else if(a%2==0) return stein(a>>1,b); else if(b%2==0) return stein(a,b>>1); return stein(abs(a-b),min(a,b));}预处理逆元(线性)LL inv[N+9];void INinv(){ mmm(inv,0); inv[1] = inv[0] = 1; for(int i = 2; i <= N ; i++) inv[i] = ( mod - mod / i ) * inv[ mod % i ] % mod;}预处理阶乘LL fac[N+9];LL inv_fac[N+9];void init_fac(){ fac[0]=fac[1]=1ll; for(int i=2;i<=N;i++)fac[i]=fac[i-1]*i%mod; //预处理阶乘逆元 inv_fac[N]=swift(fac[N],mod-2);//费马小定理求 N！的逆元 for(D i=N-1;i>=1;i--) inv_fac[i]=(inv_fac[i+1]*(i+1))%mod; inv_fac[0]=1;} 素数筛 int pri[N+9>>1],nowp;bool ispri[N+9];void init_pri(){ for(int i=2;i<=N;i++)ispri[i]=1; for(int i=2;i<=N;i++){ if(ispri[i])pri[++nowp]=i; for(int j=1;j<=nowp&&pri[j]*i<=N;j++){ ispri[pri[j]*i]=1; } }} LL A(LL a,LL b){//排列数 a下 if(b>a||b<0)return 0; return fac[a]*inv_fac[a-b]%mod;}LL C(LL a,LL b){//组合数 a下 if(b>a||b<0)return 0; return fac[a]*inv_fac[a-b]%mod*inv_fac[b]%mod;}LL arrange(LL a,LL b){//a个白球,b个黑球的排列 return fac[a+b]*inv_fac[a]%mod*inv_fac[b]%mod;}LL f_yanghui(LL n,LL m){//n行m个杨辉三角数 return C(n-1,m-1);}LL stagger(LL n){//错排(n错排) return (LL)((F)fac[n]/_e+0.5);}LL stagger(LL n,LL m){//错排(n选出m错排) return C(n,m)*stagger(m);}LL catalan(LL n){//卡特兰数 return (C(2*n,n)-C(2*n,n-1)+mod)%mod;}LL catalan(LL n,LL m){//m>n return (C(n+m,n)-C(n+m,n+1)+mod)%mod;}应用： 1.n个数进栈，有h(n)种出栈方式； 2.凸n边形，用多条不相交的对角线分成三角形，有h(n-2)种可能性； 3.n个节点，有h(n)种不同的二叉搜索树 4.给n对括号排序，有h(n)种不同的正确的排序方式 5.买票找零n个50元，m个100元（一开始柜台没零钱） 6.n*n棋盘从左下角走到右上角而不穿过主对角线的走法 7.矩阵连乘的括号化 8.在圆上选择2n个点，将这些点成对连接起来使得所得到的n条线段不相交的方法数 9.9.n层阶梯矩阵切割成n个长度递增矩阵的切割法LL through(LL x,LL y){//x*y矩阵对角线穿过1*1数量 return x+y-__gcd(x,y);}LL through(LL x,LL y,LL z){//x*y*z立方体对角线穿过1*1*1数量 return x+y+z-__gcd(x,y)-__gcd(y,z)-__gcd(z,x)+__gcd(__gcd(x,y),z);}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。