登录
← 返回首页 | 代码片段 › 7 数论与数学 › 数论与数学 / 搜索
JSON MD

7 数论与数学

含 71 个代码片段
线性筛 xianxingshai 7.7.1 素数筛法
16 行
CPP JSON
【线性筛(欧拉筛 / Euler Sieve)——质数筛选】 ▪ pre(n) — 筛出 [2,n] 所有质数存入 pri 向量: 遍历 i=2..n:若 not_prime[i]==false 则 i 为质数加入 pri; 对每个已知质数 pri_j,标记 i*pri_j 为合数,若 i%pri_j==0 则 break(关键!保证每个合数只被其最小质因子筛一次) ▪ pri[] — 存储筛出的所有质数 ▪ not_prime[] — 合数标记数组 时间复杂度严格 O(N)。与传统埃氏筛 O(N log log N) 相比,常数稍大但理论更优,N 可达 1e7+。
C++ 16 行 CPP
vector<int> pri;
bool not_prime[N];
void pre(int n) {
    for (int i = 2; i <= n; i++) {
        if (!not_prime[i]) {
            pri.push_back(i);
        }
        for (int pri_j : pri) {
            if (i * pri_j > n) break;
            not_prime[i * pri_j] = true;
            if (i % pri_j == 0) {
                break;
            }
        }
    }
}
欧拉筛.返回质数的个数。 oulashai 7.7.1 素数筛法
16 行
CPP JSON
【欧拉筛(线性筛)——返回质数个数】 ▪ euler_sieve(n) — 筛出 [2,n] 所有质数并返回质数个数 cnt: 遍历 i=2..n,若 !vis[i] 则 prime[cnt++]=i;对每个已找到的质数 prime[j],标记 vis[i*prime[j]]=1,若 i%prime[j]==0 则 break。 ▪ prime[] — 按发现顺序存储质数 ▪ vis[] — 合数标记 时间复杂度严格 O(N),比 ID=24 的 `pre()` 多返回了质数个数 cnt。
C++ 16 行 CPP
int prime[MAXN];              //保存质数
int vis[MAXN];                //记录是否被筛
int euler_sieve(int n){       //欧拉筛。返回质数的个数。
    int cnt = 0;              //记录质数个数
    memset(vis,0,sizeof(vis));
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=n;i++){             //检查每个数,筛去其中的合数
        if(!vis[i]) prime[cnt++]=i;    //如果没有筛过,是质数,记录。第一个质数是2
        for(int j=0; j<cnt; j++){      //用已经得到的质数去筛后面的数
            if(i*prime[j] >n)  break;  //只筛小于等于n的数
            vis[i*prime[j]]=1;         //关键1。用x的最小质因数筛去x
            if(i%prime[j]==0)  break;  //关键2。如果不是这个数的最小质因子,结束
        }
    }
    return cnt;                        //返回小于等于n的素数的个数
}
求等比数列和 二分 7.7.1 素数筛法
28 行
CPP JSON
【求等比数列和(二分)】 质数与筛法相关模板。 核心函数: void prime_devisor(int x) — Prim最小生成树 int sakura(无参数) — 后缀数组 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 27 行 CPP
#include<cstdio>
#define R register int
int n,t,px[10005],pk[10005];
inline void prime_devisor(int x){
	if(x%2==0){
		px[++t]=2;
		while(x%2==0)pk[t]++,x/=2;
	}
	for(R i=3;i*i<=x;i+=2){
		if(x%i==0){
			px[++t]=i;
			while(x%i==0)pk[t]++,x/=i;
		}
	}
	if(x!=1)px[++t]=x,pk[t]=1;
}
inline int sakura(){
	scanf("%d",&n);
	printf("%d=",n);
	prime_devisor(n);
	for(R i=1;i<=t;i++){
		printf("%d^%d",px[i],pk[i]);
		if(i<t)printf("+");
	}
}
int QAQWQ=sakura();
int main(){}
gcd 辗转相模 7.7.1 素数筛法
8 行
CPP JSON
【gcd(辗转相模)】 质数与筛法相关模板。 核心函数: int GCD(int a,int b) — 最大公约数 int gcd(int a,int b) — 最大公约数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 8 行 CPP
#include<cstdio>
int n,a,b;
inline int GCD(int a,int b){while(b^=a^=b^=a%=b);return a;}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int main(){
	scanf("%d",&n);
	while(n--)scanf("%d%d",&a,&b),printf("%d\n",GCD(a,b));
}
Mobius函数 埃氏筛 7.7.1 素数筛法
19 行
CPP JSON
【Mobius函数(埃氏筛)】 质数与筛法相关模板。 核心函数: void get_miu(无参数) — 获取值 关键配置: N=1e7+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 18 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
const int N=1e7+3;
int i,j,n,cnt,pan[N],miu[N];
inline void get_miu(){
	for(i=1;i<=n;++i)miu[i]=1;
	for(i=2;i<=n;++i)
		if(!pan[i]){
			miu[i]=-1;
			for(j=i<<1;j<=n;j+=i)pan[j]=1,miu[j]*=(j/i%i==0)?0:-1;
		}
}
int main(){
	n=N;
	get_miu();
	for(i=1;i<=n;++i)printf("%d: %d\n",i,miu[i]);
}
Mobius函数 线筛 7.7.1 素数筛法
22 行
CPP JSON
【Mobius函数(线筛)】 质数与筛法相关模板。 核心函数: void get_miu(无参数) — 获取值 关键配置: N=1e7+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 21 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
const int N=1e7+3;
int i,j,n,cnt,pri[N>>1],pan[N],miu[N];
inline void get_miu(){
	pan[1]=1,miu[1]=1;
	for(i=2;i<=n;++i){
		if(!pan[i])pri[++cnt]=i,miu[i]=-1;
		for(j=1;j<=cnt&&i*pri[j]<=n;++j){
            pan[i*pri[j]]=1;
            if(i%pri[j])miu[i*pri[j]]=-miu[i];
            else{miu[i*pri[j]]=0;break;}
        }
	}
}
int main(){
	n=N;
	get_miu();
	for(i=1;i<=n;++i)printf("%d: %d\n",i,miu[i]);
}
最值反演 (Card Collector) Min-Max容斥 7.7.1 素数筛法
30 行
CPP JSON
【最值反演 (Card Collector)(Min-Max容斥)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=23,M=1048576+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 29 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=23,M=1048576+3;
int n,V,cnt[M];LD ans,p[N],Min[M];
inline void in(Re &x){
    int f=0;x=0;char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    x=f?-x:x;
}
int main(){
//    freopen("123.txt","r",stdin);
    while(~scanf("%d",&n)){
        V=(1<<n)-1,ans=0;
        for(Re i=1;i<=n;++i)scanf("%lf",&p[i]);
        for(Re s=1;s<=V;++s){
            Min[s]=0,cnt[s]=cnt[s>>1]+(s&1);
            for(Re i=1;i<=n;++i)if(s&(1<<i-1))Min[s]+=p[i];
            Min[s]=1.0/Min[s];
        }
        for(Re t=1;t<=V;++t)ans+=(cnt[t]&1)?Min[t]:-Min[t];
        printf("%lf\n",ans);
    }
}
杜教筛 map 7.7.1 素数筛法
56 行
CPP JSON
【杜教筛(map)】 杜教筛模板,O(N^(2/3)) 求积性函数前缀和。 核心函数: void in(Re &x) — 核心算法函数 void get_(Re N) — 获取值 LL get_Sphi(Re n) — 获取值 int get_Smiu(Re n) — 获取值 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Re register int
#define LL long long
using namespace std;
const int N23=1664511+3,N=2147483647;
int x,T,cnt,pan[N23],pri[N23],phi[N23],miu[N23];
int TO,Smiu[N23];LL Sphi[N23];
map<int,int>Smiu_;map<int,LL>Sphi_;
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void get_(Re N){
	miu[1]=phi[1]=pan[1]=1;
	for(Re i=2;i<=N;++i){
		if(!pan[i])pri[++cnt]=i,miu[i]=-1,phi[i]=i-1;
		for(Re j=1;j<=cnt&&pri[j]<=N/i;++j){
			pan[i*pri[j]]=1;
			if(i%pri[j])miu[i*pri[j]]=-miu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];
			else{miu[i*pri[j]]=0,phi[i*pri[j]]=phi[i]*pri[j];break;}
		}
	}
	for(Re i=1;i<=N;++i)Smiu[i]=Smiu[i-1]+miu[i],Sphi[i]=Sphi[i-1]+phi[i];
}
inline LL get_Sphi(Re n){
	if(n<=TO)return Sphi[n];
	if(Sphi_[n])return Sphi_[n];
	LL ans=(LL)n*(n+1)>>1;
	for(Re l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ans-=(LL)(r-l+1)*get_Sphi(n/l);
	}
	return Sphi_[n]=ans;
}
inline int get_Smiu(Re n){
	if(n<=TO)return Smiu[n];
	if(Smiu_[n])return Smiu_[n];
	Re ans=1;
	for(Re l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ans-=(r-l+1)*get_Smiu(n/l);
	}
	return Smiu_[n]=ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T),get_(TO=N23-3);
	while(T--)in(x),printf("%lld %d\n",get_Sphi(x),get_Smiu(x));
}
杜教筛 数组记忆化 7.7.1 素数筛法
63 行
CPP JSON
【杜教筛(数组记忆化)】 杜教筛模板,O(N^(2/3)) 求积性函数前缀和。 核心函数: void in(Re &x) — 核心算法函数 void get_(Re N) — 获取值 LL get_Sphi(Re n) — 获取值 int get_Smiu(Re n) — 获取值 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define Re register int
#define LL long long
using namespace std;
const int N23=1664511+3,N13=1303,N=2147483647;
int x,T,cnt,pan[N23],pri[N23],phi[N23],miu[N23];
int TO,vis1[N13],vis2[N13],Smiu[N23],Smiu_[N13];
LL Sphi[N23],Sphi_[N13];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void get_(Re N){
	miu[1]=phi[1]=pan[1]=1;
	for(Re i=2;i<=N;++i){
		if(!pan[i])pri[++cnt]=i,miu[i]=-1,phi[i]=i-1;
		for(Re j=1;j<=cnt&&pri[j]<=N/i;++j){
			pan[i*pri[j]]=1;
			if(i%pri[j])miu[i*pri[j]]=-miu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]];
			else{miu[i*pri[j]]=0,phi[i*pri[j]]=phi[i]*pri[j];break;}
		}
	}
	for(Re i=1;i<=N;++i)Smiu[i]=Smiu[i-1]+miu[i],Sphi[i]=Sphi[i-1]+phi[i];
}
inline LL get_Sphi(Re n){
	if(n<=TO)return Sphi[n];
	Re nn=N/n;
	if(vis1[nn])return Sphi_[nn];
	LL ans=(LL)n*(n+1)>>1;
	for(Re l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ans-=(LL)(r-l+1)*get_Sphi(n/l);
	}
	vis1[nn]=1;
	return Sphi_[nn]=ans;
}
inline int get_Smiu(Re n){
	if(n<=TO)return Smiu[n];
	Re nn=N/n;
	if(vis2[nn])return Smiu_[nn];
	Re ans=1;
	for(Re l=2,r;l<=n;l=r+1){
		r=n/(n/l);
		ans-=(r-l+1)*get_Smiu(n/l);
	}
	vis2[nn]=1;
	return Smiu_[nn]=ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T),get_(TO=N23-3);
	while(T--){
		in(x),printf("%lld %d\n",get_Sphi(x),get_Smiu(x));
		memset(vis1,0,sizeof(vis1));
		memset(vis2,0,sizeof(vis2));
	}
}
欧拉函数 暴力) sqrt(n 7.7.1 素数筛法
17 行
CPP JSON
【欧拉函数 暴力)(sqrt(n)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: int phi(Re x) — 核心算法函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 16 行 CPP
#include<cstdio>
#define Re register int
int n;
inline int phi(Re x){
	Re ans=x;
	for(Re i=2;i*i<=x;i++)
		if(x%i==0){
			ans/=i,ans*=i-1;
			while(x%i==0)x/=i;
		}
	if(x>1)ans/=x,ans*=x-1;
	return ans;
}
int main(){
	scanf("%d",&n),printf("%d\n",phi(n));
}
欧拉函数 埃氏筛 7.7.1 素数筛法
17 行
CPP JSON
【欧拉函数(埃氏筛)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: void get_phi(无参数) — 获取值 关键配置: N=1e6 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 16 行 CPP
#include<cstdio>
const int N=1e6;
int cnt,n=N,phi[N/3],pan[N],pri[N];
inline void get_phi(){
	phi[1]=1;
    for(int i=2;i<=n;i++)if(!phi[i]){
    	for(int j=i;j<=n;j+=i){
            if(!phi[j])phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
}
int main(){
	get_phi();
	for(int i=1;i<=n;++i)printf("%d: %d\n",i,phi[i]);
}
欧拉函数 线筛 7.7.1 素数筛法
21 行
CPP JSON
【欧拉函数(线筛)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: void get_phi(int N) — 获取值 关键配置: N=1e6 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 20 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
const int N=1e6;
int cnt,i,j,pan[N+1],pri[N/3],phi[N+1];
inline void get_phi(int N){
    pan[1]=1,phi[1]=1;
    for(int i=2;i<=N;++i){
        if(!pan[i])pri[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&pri[j]<=N/i;++j){
            pan[i*pri[j]]=1;
            if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1);
            else{phi[i*pri[j]]=phi[i]*pri[j];break;}
        }
    }
}
int main(){
	get_phi(N);
	for(i=1;i<=N;++i)printf("%d: %d\n",i,phi[i]);
}
Power Tower (欧拉定理) 炸勃龙弱化 7.7.1 素数筛法
48 行
CPP JSON
【Power Tower (欧拉定理)(炸勃龙弱化)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: void in(Re &x) — 核心算法函数 LL Phi(Re x) — 核心算法函数 LL mi(Re x,Re k,Re P) — 核心算法函数 LL sakura(Re l,Re r,Re P) — 后缀数组 关键配置: N=1e5+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 47 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define Re register LL
using namespace std;
const int N=1e5+3;
LL n,l,r,T,P,fu,a[N];char ch;map<LL,LL>phi;
inline void in(Re &x){
    x=fu=0;ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=fu?-x:x;
}
inline LL Phi(Re x){
    Re ans=x,pos=x;
    if(phi.count(x))return phi[x];
    for(Re i=2;i<=sqrt(x);i++)
        if(!(x%i)){
            ans=ans/i*(i-1);
            while(!(x%i)) x/=i;
        }
    if(x>1)ans=ans/x*(x-1);
    return phi[pos]=ans;
}
inline LL mi(Re x,Re k,Re P){
    Re s=1,ok=0,flag=0;ok|=(x>=P);x%=P;
    while(k){
        if(k&1){s*=x;flag|=(ok||s>=P);s%=P;}
        x*=x;ok|=(x>=P);x%=P;k>>=1;
    }
    return s+(flag?P:0);
}
inline LL sakura(Re l,Re r,Re P){
    if(P==1|l>r)return 1;
    return mi(a[l],sakura(l+1,r,Phi(P)),P);
}
int main(){
    in(n),in(P);
    for(Re i=1;i<=n;++i)in(a[i]);
    in(T);
    while(T--){
        in(l),in(r);
    	printf("%lld\n",sakura(l,r,P)%P);
    }
}
BSGS拔山盖世 可爱的质数 7.7.1 素数筛法
38 行
CPP JSON
【BSGS拔山盖世(可爱的质数)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 关键配置: N=1e5+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 37 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int x,y,m,P;map<int,int>B;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
//x^k = y (mod P)
//k = am-b (m=sqrt(P)+1, a\in[1,m], b\in[0,m-1])
//(x^m)^a = y x^b (mod P)
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(P),in(x),in(y),m=sqrt(P)+1;
	for(Re b=0,s=y;b<m;++b)B[s]=b,s=(LL)s*x%P;
	Re tmp=mi(x,m);
	for(Re a=1,s=1;a<=m;++a){
		s=(LL)s*tmp%P;
		if(B.find(s)!=B.end()){printf("%d\n",a*m-B[s]);return 0;}
	}
	puts("no solution");
}
CRT中国剩余定理 (P两两互质) 同余方程组 7.7.1 素数筛法
35 行
CPP JSON
【CRT中国剩余定理 (P两两互质)(同余方程组)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 void exgcd(Re a,Re b,Re &x,Re &y) — 最大公约数 LL cf(Re x,Re k,Re P) — 核心算法函数 关键配置: N=13 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 34 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
const int N=13;
LL n,ans,lcm=1,a[N],m[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void exgcd(Re a,Re b,Re &x,Re &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,x,y);Re x0=x,y0=y;
	x=y0,y=x0-a/b*y0;return;
}
inline LL cf(Re x,Re k,Re P){
	Re s=0;
	while(k){
		if(k&1)(s+=x)%=P;
		(x+=x)%=P,k>>=1;
	}
	return s;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)in(m[i]),in(a[i]),lcm*=m[i];
    for(Re i=1;i<=n;++i){
		Re x,y,M=lcm/m[i];exgcd(M,m[i],x,y);//M[i]*inv+m[i]*y=1
		x=(x%m[i]+m[i])%m[i],(ans+=cf(cf(a[i],M,lcm),x,lcm))%=lcm;
	}
	printf("%lld\n",ans);
}
EXBSGS扩展拔山盖世 mi 7.7.1 素数筛法
50 行
CPP JSON
【EXBSGS扩展拔山盖世】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k,Re P) — 核心算法函数 int gcd(Re a,Re b) — 最大公约数 void exBSGS(Re x,Re y,Re P) — SG函数计算 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 49 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define Re register int
using namespace std;
int x,y,z;map<int,int>B;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k,Re P){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int gcd(Re a,Re b){return !b?a:gcd(b,a%b);}
inline void exBSGS(Re x,Re y,Re P){
	if(y==1){puts("0");return;}
	Re d=gcd(x,P),tmp=1,t=0;
	while(d!=1){
		if(y%d){puts("No Solution");return;}
		++t,y/=d,P/=d,tmp=(LL)tmp*(x/d)%P;
		if(y==tmp){printf("%d\n",t);return;}
		d=gcd(x,P);
	}
	Re m=sqrt(P)+1;B.clear();
	for(Re b=0,s=y;b<m;++b)B[s]=b,s=(LL)s*x%P;
	Re s=tmp;tmp=mi(x,m,P);
	for(Re a=1;a<=m;++a){
		s=(LL)s*tmp%P;
		if(B.find(s)!=B.end()){printf("%d\n",a*m-B[s]+t);return;}
	}
	puts("No Solution");
}
int main(){
//	freopen("123.txt","r",stdin);
	while(1){
		in(x),in(y),in(z);
		if(!x&&!y&&!z)break;
		exBSGS(x,z,y);
	}
}
EXCRT扩展中国剩余定理 P不一定两两互质 7.7.1 素数筛法
38 行
CPP JSON
【EXCRT扩展中国剩余定理(P不一定两两互质)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 LL exgcd(Re a,Re b,Re &x,Re &y) — 最大公约数 LL cf(Re x,Re k,Re P) — 核心算法函数 关键配置: N=1e5+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 37 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e5+3;
LL n,ans,lcm=1,a[N],m[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LL exgcd(Re a,Re b,Re &x,Re &y){
	if(!b){x=1,y=0;return a;}
	Re gcd=exgcd(b,a%b,x,y);Re x0=x,y0=y;
	x=y0,y=x0-a/b*y0;return gcd;
}
inline LL cf(Re x,Re k,Re P){
	Re s=0;
	while(k){
		if(k&1)(s+=x)%=P;
		(x+=x)%=P,k>>=1;
	}
	return s;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)in(m[i]),in(a[i]),lcm*=m[i];
    ans=a[1]%m[1],lcm=m[1];
    for(Re i=2;i<=n;++i){//ans+lcm*k=a[i](mod m[i]) -> lcm*k=a[i]-ans(mod m[i]) -> lcm*k+m[i]*y=a[i]-ans
		Re c=((a[i]-ans)%m[i]+m[i])%m[i],x,y;
		Re gcd=exgcd(lcm,m[i],x,y);
		Re k=cf(x,c/gcd,m[i]/gcd);
		ans+=lcm*k,lcm*=m[i]/gcd,ans=(ans%lcm+lcm)%lcm;
	}
	printf("%lld\n",ans);
}
EXGCD 线性同余方程 7.7.1 素数筛法
13 行
CPP JSON
【EXGCD(线性同余方程)】 质数与筛法相关模板。 核心函数: void exgcd(Re a,Re b,Re &x,Re &y) — 最大公约数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 12 行 CPP
#include<cstdio>
#define Re register int
int a,b,x,y;
inline void exgcd(Re a,Re b,Re &x,Re &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,x,y);Re x0=x,y0=y;
	x=y0,y=x0-a/b*y0;return;
}
int main(){
    scanf("%d%d",&a,&b),exgcd(a,b,x,y);
	printf("%d\n",(x%b+b)%b);
}
二次剩余 mi 7.7.1 素数筛法
56 行
CPP JSON
【二次剩余】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 CP mi_(CP x,Re k) — 核心算法函数 LL Sqrt(Re n) — 开平方 核心结构体:CP 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
int n,T,P,W,det;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
struct CP{
	int x,y;CP(Re X=0,Re Y=0){x=X,y=Y;}
	inline CP operator*(const CP &O)const{return CP(((LL)x*O.x%P+(LL)y*O.y%P*W%P)%P,((LL)x*O.y%P+(LL)y*O.x%P)%P);}
	inline CP operator*=(const CP &O){return *this=*this*O;}
};
inline CP mi_(CP x,Re k){
	CP s=CP(1,0);
	while(k){
		if(k&1)s*=x;
		x*=x,k>>=1;
	}
	return s;
}
inline LL Sqrt(Re n){
    if(!n)return 0;Re x;
    while(1){
        x=rand()%P,W=((LL)x*x%P-n+P)%P;
        if(mi(W,(P-1)/2)==P-1)break;
    }
    return mi_(CP(x,1),(P+1)/2).x;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		in(n),in(P);
		if(mi(n,(P-1)/2)==P-1)puts("Hola!");//�޽�
	    else{
		    det=Sqrt(n);
		    if(det)printf("%d %d\n",min(det,P-det),max(det,P-det));
		    else printf("%d\n",det);
		}
	}
}
扩展欧拉定理 a^b%m 7.7.1 素数筛法
26 行
CPP JSON
【扩展欧拉定理(a^b%m)】 线性筛(欧拉筛)模板,O(N) 筛出质数并可同时计算积性函数。 核心函数: LL cf(Re x,Re k) — 核心算法函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 25 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cctype>
#define LL long long
#define Re register LL
LL i,a,b,m,x,s,phi,flag;char c;
inline LL cf(Re x,Re k){
	Re s=0;
	while(k){
		if(k&1)(s+=x)%=m;
		(x<<=1)%=m,k>>=1;
	}
	return s;
}
int main(){
    scanf("%lld%lld",&a,&m);phi=x=m;
    for(i=2;i*i<=m;++i)if(!(x%i)){phi-=phi/i;while(!(x%i))x/=i;}
    if(x>1)phi-=phi/x;
    while(!isdigit(c=getchar()));
    while(isdigit(c))flag|=((b=(b<<1)+(b<<3)+(c^48))>=phi),b%=phi,c=getchar();
    b+=flag?phi:0;x=1;
    while(b){if(b&1)x=cf(x,a)%m;a=cf(a,a)%m,b>>=1;}
    printf("%lld",x);
}
有理数取模 mi 7.7.1 素数筛法
25 行
CPP JSON
【有理数取模】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 LL mi(Re x,Re k) — 核心算法函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛) 说明:freopen("123.txt","r",stdin);
C++ 25 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const LL N=1e4+3,P=19260817;
LL a,b;
inline void in(Re &x){
    Re f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),x%=P,c=getchar();
}
inline LL mi(Re x,Re k){
    Re s=1;
    while(k){
        if(k&1)(s*=x)%=P;
        (x*=x)%=P,k>>=1;
    }
    return s;
}
int main(){
    // freopen("123.txt","r",stdin);
    in(a),in(b);
    if(b)printf("%lld\n",a%P*mi(b,P-2)%P);
    else puts("Angry!");
}
逆元 快速幂 7.7.1 素数筛法
17 行
CPP JSON
【逆元(快速幂)】 质数与筛法相关模板。 核心函数: int inv(Re x,Re P) — 求模逆元 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 16 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
int n,P;
inline int inv(Re x,Re P){
    Re s=1,k=P-2;
    while(k){
    	if(k&1)s=(LL)s*x%P;
    	x=(LL)x*x%P,k>>=1;
    }
    return s%P;
}
int main(){
    scanf("%d%d",&n,&P);
    for(Re i=1;i<=n;++i)printf("%d\n",inv(i,P));
}
逆元 递推 7.7.1 素数筛法
12 行
CPP JSON
【逆元(递推)】 质数与筛法相关模板。 关键配置: N=3e6+3 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 11 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
const int N=3e6+3;
int n,P,inv[N];
int main(){
    scanf("%d%d",&n,&P);
    inv[1]=1;
    for(Re i=2;i<=n;++i)inv[i]=(LL)(P-P/i)*inv[P%i]%P;
    for(Re i=1;i<=n;++i)printf("%d\n",inv[i]);
}
炸勃龙 树状数组+扩展欧拉定理 7.7.1 素数筛法
47 行
CPP JSON
【炸勃龙(树状数组+扩展欧拉定理)】 质数与筛法相关模板。 核心函数: void in(Re &x) — 核心算法函数 void add(Re x,Re k) — 加法更新 LL ask(Re x) — 核心算法函数 LL mi(Re x,Re k,Re P) — 核心算法函数 LL sakura(Re l,Re r,Re P) — 后缀数组 关键配置: N=5e5+3,Np=2e7 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 46 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#define LL long long
#define Re register LL
#define F(a,b) for(i=a;i<=b;++i)
const int N=5e5+3,Np=2e7;
LL i,j,n,x,l,r,K,T,fu,cnt,c[N],C[N],pan[Np+1],pri[Np+1],phi[Np+1];char ch;
inline void in(Re &x){
    x=fu=0;ch=getchar();
    while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=fu?-x:x;
}
inline void add(Re x,Re k){while(x<=n)C[x]+=k,x+=x&-x;}
inline LL ask(Re x){Re tmp=0;while(x)tmp+=C[x],x-=x&-x;return tmp;}
inline LL mi(Re x,Re k,Re P){
    Re s=1,ok=0,flag=0;ok|=(x>=P);x%=P;
    while(k){
        if(k&1){s*=x;flag|=(ok||s>=P);s%=P;}
        x*=x;ok|=(x>=P);x%=P;k>>=1;
    }
    return s+(flag?P:0);
}

inline LL sakura(Re l,Re r,Re P){
    if(P==1|l>r)return 1;
    return mi(ask(l),sakura(l+1,r,phi[P]),P);
}
int main(){
    for(i=2;i<=Np;++i){
        if(!pan[i])pri[++cnt]=i,phi[i]=i-1;
        for(j=1;j<=cnt;++j){
      		if(i*pri[j]>Np)break;
      		pan[i*pri[j]]=1;
      		if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1);
      		else{phi[i*pri[j]]=phi[i]*pri[j];break;}
   		}
    }
    in(n),in(T);
    F(1,n)in(x),add(i,x-l),l=x;
    while(T--){
        in(K),in(l),in(r),in(x);
        if(K<2)add(l,x),add(r+1,-x);
        else printf("%lld\n",sakura(l,r,x)%x);
    }
}
判素数 Miller Rabin 7.7.1 素数筛法
40 行
CPP JSON
【判素数(Miller Rabin)】 质数与筛法相关模板。 核心函数: LL cf(Re x,Re k,Re P) — 核心算法函数 LL mi(Re x,Re k,Re P) — 核心算法函数 bool Miller_Rabin(Re x) — 核心算法函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 39 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
LL n,prime[10]={2,3,5,7,11,13,17,19,23,29};
inline LL cf(Re x,Re k,Re P){
	Re s=0;
	while(k){
		if(k&1)(s+=x)%=P;
		(x<<=1)%=P,k>>=1;
	}
	return s%P;
}
inline LL mi(Re x,Re k,Re P){
	Re s=1;
    while(k){
    	if(k&1)s=cf(s,x,P)%P;
    	x=cf(x,x,P)%P,k>>=1;
    }
    return s%P;
}
inline bool Miller_Rabin(Re x){
    Re s=0,t=x-1;
    if(x==2)return 1;
    if(x<2||!(x&1))return 0;
    while(!(t&1))s++,t>>=1;
    for(Re i=0;i<10&&prime[i]<x;++i){
        Re a=prime[i],b=mi(a,t,x);
        for(Re j=1,k;j<=s;++j){
            k=cf(b,b,x);
            if(k==1&&b!=1&&b!=x-1)return 0;
            b=k;
        }
        if(b!=1)return 0;
    }
    return 1;
}
int main(){
	while(scanf("%lld",&n)!=EOF)puts(Miller_Rabin(n)?"Y":"N");
}
判素数 暴力 7.7.1 素数筛法
16 行
CPP JSON
【判素数(暴力)】 质数与筛法相关模板。 核心函数: bool judge(int n) — 判定函数 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 15 行 CPP
#include<cstdio>
#include<cmath>
int x;
inline bool judge(int n){
	if(n<4)return 1;
	if(n%2==0)return 0;
	int half=sqrt(n);
	for(int i=3;i<=half;i+=2)
		if(n%i==0)return 0;
	return 1;
}
int main(){
	scanf("%d",&x);
	puts(judge(x)?"YES":"NO");
}
筛素数 埃氏筛 7.7.1 素数筛法
17 行
CPP JSON
【筛素数(埃氏筛)】 质数与筛法相关模板。 核心函数: void creat_prime(无参数) — Prim最小生成树 int sakura(无参数) — 后缀数组 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 16 行 CPP
#include<cstdio>
#define R register int
int pri[10005],pan[10005],gs;
inline void creat_prime(){
	for(R i=2;i<=10000;i++)
		if(pan[i]==0){
			pri[++gs]=i;
			for(R j=2;i*j<=10000;j++)pan[i*j]=1;
		}
}
inline int sakura(){
	creat_prime();
	for(R i=1;i<=gs;i++)printf("%d\n",pri[i]);
}
int QAQWQ=sakura();
int main(){}
筛质数 线筛 7.7.1 素数筛法
18 行
CPP JSON
【筛质数(线筛)】 质数与筛法相关模板。 核心函数: void get_pri(无参数) — 获取值 关键配置: N=1e6 复杂度:O(N)(线性筛)或 O(N log log N)(埃氏筛)
C++ 18 行 CPP
#include<cstdio>
#include<ctime>
const int N=1e6;
int cnt,i,j,pri[N/3];bool pan[N+1];
inline void get_pri(){
	pan[0]=pan[1]=1;
	for(i=2;i<=N;++i){
		if(!pan[i])pri[++cnt]=i;
		for(j=1;j<=cnt&&i*pri[j]<=N;++j){
			pan[i*pri[j]]=1;
			if(i%pri[j]==0)break;
		}
	}
}
int main(){
	get_pri();
	for(j=0,i=1;i<=cnt;++i)printf("%d ",pri[i]);
}
167 行
CPP JSON
【组合数学工具类 Combinatorics】 ▪ Combinatorics(n) — 构造函数,预处理 [0,n] 的阶乘 fact[] 和逆阶乘 inv_fact[],O(N) ▪ qpow(a, b) — 快速幂(内部使用),用于求逆元,O(log MOD) ▪ inv(x) — 求 x 的模逆元:qpow(x, MOD-2)(费马小定理,需 MOD 为质数) ▪ C(n, k) — 组合数 C(n,k) = fact[n] * inv_fact[k] * inv_fact[n-k] % MOD,O(1) ▪ A(n, k) — 排列数 A(n,k) = fact[n] * inv_fact[n-k] % MOD,O(1) ▪ Lucas(n, k) — 卢卡斯定理求 C(n,k)%MOD,适用于 n,k 很大但 MOD 较小(质数),O(log_MOD n) ▪ Stirling2(n, k) — 第二类斯特林数 S(n,k),n 个元素划分为 k 个非空子集的方案数,O(nk)
C++ 167 行 CPP
class Combinatorics {
private:
    vector<ll> fact, inv_fact;
    int max_n;
    
public:
    // 预处理阶乘和逆阶乘,O(n)
    Combinatorics(int n) : max_n(n) {
        fact.resize(n + 1);
        inv_fact.resize(n + 1);
        
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        
        inv_fact[n] = inv(fact[n]);
        for (int i = n - 1; i >= 0; i--) {
            inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
        }
    }
    
    // 快速幂计算逆元,O(log MOD)
    ll inv(ll x) {
        return qpow(x, MOD - 2);
    }
    
    // 快速幂,O(log exponent)
    ll qpow(ll a, ll b) {
        ll res = 1;
        while (b) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    
    // 组合数C(n,k),O(1)
    ll C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
    }
    
    // 排列数A(n,k),O(1)
    ll A(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * inv_fact[n - k] % MOD;
    }
    
    // 卢卡斯定理计算组合数,适用于n,k很大但MOD较小的情况
    ll Lucas(ll n, ll k) {
        if (k == 0) return 1;
        return C(n % MOD, k % MOD) * Lucas(n / MOD, k / MOD) % MOD;
    }
    
    // 第二类斯特林数S(n,k),将n个元素划分为k个非空子集,O(nk)
    ll Stirling2(int n, int k) {
        ll res = 0;
        for (int i = 0; i <= k; i++) {
            ll term = C(k, i) * qpow(i, n) % MOD;
            if ((k - i) % 2) {
                res = (res - term + MOD) % MOD;
            } else {
                res = (res + term) % MOD;
            }
        }
        return res * inv_fact[k] % MOD;
    }
    
    // 贝尔数B(n),基于第二类斯特林数的实现,O(n^2)
    // B(n) = Σ S(n,k) for k=0 to n
    ll Bell_Stirling(int n) {
        ll res = 0;
        for (int k = 0; k <= n; k++) {
            res = (res + Stirling2(n, k)) % MOD;
        }
        return res;
    }
    
    // 贝尔数B(n),基于动态规划的实现,O(n^2)
    // 使用递推关系:B(n+1) = Σ C(n,k)*B(k) for k=0 to n
    ll Bell_DP(int n) {
        if (n == 0) return 1;
        vector<ll> bell(n + 1);
        bell[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            bell[i] = 0;
            for (int k = 0; k < i; k++) {
                bell[i] = (bell[i] + C(i - 1, k) * bell[k]) % MOD;
            }
        }
        return bell[n];
    }
    
    // 卡特兰数,O(1)
    ll Catalan(int n) {
        return C(2 * n, n) * inv(n + 1) % MOD;
    }
    
    // 错位排列数,O(n)预处理后O(1)查询
    ll Derangement(int n) {
        if (n == 0) return 1;
        if (n == 1) return 0;
        // D(n) = (n-1)*(D(n-1)+D(n-2))
        vector<ll> d(n + 1);
        d[0] = 1;
        d[1] = 0;
        for (int i = 2; i <= n; i++) {
            d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % MOD;
        }
        return d[n];
    }
    
    // 计算gcd,O(log min(a,b))
    ll gcd(ll a, ll b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    // 计算lcm,O(log min(a,b))
    ll lcm(ll a, ll b) {
        return a / gcd(a, b) * b;
    }
    
    // 扩展欧几里得算法,求解ax + by = gcd(a,b)
    ll ext_gcd(ll a, ll b, ll &x, ll &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        ll d = ext_gcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
    
    // 中国剩余定理,求解x ≡ a_i (mod m_i)
    ll CRT(const vector<ll> &a, const vector<ll> &m) {
        ll M = 1, x = 0;
        int n = a.size();
        for (int i = 0; i < n; i++) M *= m[i];
        
        for (int i = 0; i < n; i++) {
            ll Mi = M / m[i];
            ll y, z;
            ext_gcd(Mi, m[i], y, z);
            x = (x + a[i] * Mi % M * y % M) % M;
        }
        return (x + M) % M;
    }
    
    // 欧拉函数,计算小于n且与n互质的数的个数,O(sqrt(n))
    ll EulerPhi(ll n) {
        ll res = n;
        for (ll i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = res / i * (i - 1);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1) res = res / n * (n - 1);
        return res;
    }
};

Combinatorics comb(1000000); // 预处理1e6以内的阶乘
47 行
CPP JSON
【Polya定理】 组合数学与计数模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 int phi(Re x) — 核心算法函数 关键配置: N=1e6+3,P=1e9+7 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 46 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e6+3,P=1e9+7;
int n,T,pri[N/3];bool pan[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline int phi(Re x){
	Re ans=x;
	for(Re i=2;i*i<=x;i++)
		if(x%i==0){
			ans/=i,ans*=i-1;
			while(x%i==0)x/=i;
		}
	if(x>1)ans/=x,ans*=x-1;
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		in(n);Re ans=0;
		for(Re i=1;i*i<=n;++i)
			if(n%i==0){
				(ans+=(LL)mi(n,i-1)*phi(n/i)%P)%=P;
				if(i!=n/i)(ans+=(LL)mi(n,n/i-1)*phi(i)%P)%=P;
			}
		printf("%d\n",ans);
	}
}
卡特兰数Catalan 质因数分解 取模 7.7.2 组合数学与计数
25 行
CPP JSON
【卡特兰数Catalan(质因数分解 取模)】 卡特兰数(Catalan Number)模板,常见于括号序列、出栈序列等计数。 核心函数: void get_pri(Re N) — 获取值 LL Catalan(Re n) — 核心算法函数 关键配置: N=1e6+3 适用场景:计数问题、排列组合求值(含模运算)
C++ 24 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
const int N=1e6+3;
LL n,P,cnt,pri[N],pan[N<<1];
inline void get_pri(Re N){
    for(Re i=2;i<=N;++i){
        if(!pan[i])pri[++cnt]=i;
        for(Re j=1;j<=cnt&&i*pri[j]<=N;++j)pan[i*pri[j]]=1;
    }
}
inline LL Catalan(Re n){
    Re ans=1;cnt=0;get_pri(n<<1);
    for(Re i=1;i<=cnt;i++){
        Re x=pri[i],t=0;
        while(x<=2*n){t+=2*n/x-n/x-(n+1)/x;x*=pri[i];}
        while(t--)(ans*=pri[i])%=P;
    }
    return ans%P;
}
int main(){
    scanf("%lld%lld",&n,&P);
	printf("%lld",Catalan(n));
}
卡特兰数Catalan 质因数分解 高精度 7.7.2 组合数学与计数
22 行
CPP JSON
【卡特兰数Catalan(质因数分解 高精度)】 卡特兰数(Catalan Number)模板,常见于括号序列、出栈序列等计数。 核心函数: void cf(int x) — 核心算法函数 适用场景:计数问题、排列组合求值(含模运算)
C++ 21 行 CPP
#include<cstdio>
#define R register int
int n,t,x,len,ans[100000],pan[120005];
void cf(int x){
    R i,j;
    for(i=1;i<=len;i++)ans[i]*=x;
    len+=6;
    for(i=1;i<=len;i++)ans[i+1]+=ans[i]/10,ans[i]%=10;
    while(!ans[len])len--;
}
int main(){
    scanf("%d",&n);R i,j;len=ans[1]=1;
    for(i=2;i<=2*n;i++)
        if(pan[i]==0){
            x=i;t=0;
            while(x<=2*n){t+=2*n/x-n/x-(n+1)/x;x*=i;}
            while(t--)cf(i);
            for(j=i;j<=2*n/i;j++)pan[i*j]=1;
        }
    for(i=len;i>=1;i--)printf("%d",ans[i]);
}
37 行
CPP JSON
【卢卡斯定理】 Lucas 定理模板,用于大组合数对质数取模。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 int C(Re m,Re n) — 核心算法函数 int Lucas(Re m,Re n) — 卢卡斯定理 关键配置: N=1e5+3 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 36 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
int n,m,P,T,jc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline int C(Re m,Re n){
	return m>n?0:(LL)jc[n]*inv(jc[m])%P*inv(jc[n-m])%P;
}
inline int Lucas(Re m,Re n){
	return m==0?1:(LL)Lucas(m/P,n/P)*C(m%P,n%P)%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		in(n),in(m),in(P),jc[0]=1;
		for(Re i=1;i<=P-1;++i)jc[i]=(LL)jc[i-1]*i%P;
		printf("%d\n",Lucas(n,n+m));
	}
}
康托展开 optimize 7.7.2 组合数学与计数
21 行
CPP JSON
【康托展开】 组合数学与计数模板。 核心函数: void add(int x) — 加法更新 int ask(int x) — 核心算法函数 关键配置: N=1e6+5,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 20 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#define LL long long
const int N=1e6+5,P=998244353;
int n,i,ans,a[N],g[N],C[N],jc[N]={1};
inline void add(int x){while(x<=n)++C[x],x+=x&-x;}
inline int ask(int x){
	int ans=0;
	while(x)ans+=C[x],x-=x&-x;
	return ans;
}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;++i)scanf("%d",&a[i]);
	for(i=n;i;--i)g[i]=ask(a[i]-1),add(a[i]);
	for(i=1;i<=n;++i)jc[i]=(LL)jc[i-1]*i%P;
	for(i=1;i<=n;++i)(ans+=(LL)g[i]*jc[n-i]%P)%=P;
	printf("%d",ans+1);
}
球盒模型全套 Cat 7.7.2 组合数学与计数
61 行
CPP JSON
【球盒模型全套(Cat)】 组合数学与计数模板。 核心函数: void in(Re &x) — 核心算法函数 LL mi(Re x,Re k) — 核心算法函数 LL niv(Re x) — 核心算法函数 LL c(Re m,Re n) — 核心算法函数 void Stirling(无参数) — 核心算法函数 void DP(无参数) — 核心算法函数 LL Catalan(Re n) — 核心算法函数 说明:freopen("cat.in","r",stdin);;freopen("cat.out","w",stdout); 适用场景:计数问题、排列组合求值(含模运算)
C++ 60 行 CPP
#include<cstdio>
#define LL long long
#define Re register LL
const int P=998244353,N=1e6+5;
LL T,a,b,f,opt,cnt,jc[N*2+5],dp[205][205],S[105][105];
inline void in(Re &x){
    x=f=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f)x=-x;
}
inline LL mi(Re x,Re k){
    Re ans=1;
    while(k){
        if(k&1)ans=(ans*x)%P;
        x=(x*x)%P;k>>=1;
    }
    return ans%P;
} 
inline LL niv(Re x){return mi(x,P-2);}
inline LL c(Re m,Re n){
    if(n<m)return 0;
    if(n<P)return jc[n]*niv(jc[m])%P*niv(jc[n-m])%P;
    return c(m/P,n/P)*c(m%P,n%P)%P;
}
inline void Stirling(){
    for(Re i=0;i<=100;++i)S[i][i]=1;
    for(Re i=1;i<=100;++i)
        for(Re j=1;j<=100;++j)
            S[i][j]=(S[i-1][j-1]+S[i-1][j]*j%P)%P;
}
inline void DP(){
    dp[0][0]=1;
    for(Re i=1;i<=200;++i)
        for(Re j=1;j<=i;++j)
            dp[i][j]=(dp[i-j][j]+dp[i-1][j-1])%P;
}
inline LL Catalan(Re n){return c(n,n<<1)*niv(n+1)%P;}
int main(){
//  freopen("cat.in","r",stdin);
//  freopen("cat.out","w",stdout);
    jc[0]=1;for(Re i=1;i<=N*2;i++)jc[i]=jc[i-1]*i%P;
    in(T);Stirling();DP();
    while(T--){
        in(opt),in(a),in(b);
        if(opt==1)printf("%lld\n",mi(b,a));
        else if(opt==2)printf("%lld\n",c(b-1,a-1));
        else if(opt==3)printf("%lld\n",c(b-1,a+b-1));
        else if(opt==4)printf("%lld\n",S[a][b]);
        else if(opt==5)printf("%lld\n",jc[b]*S[a][b]%P);
        else if(opt==6){
            Re ans=0;
            for(Re i=1;i<=b;++i)(ans+=S[a][i])%=P;
            printf("%lld\n",ans);
        }
        else if(opt==7)printf("%lld\n",dp[a+b][b]);
        else if(opt==8)printf("%lld\n",dp[a][b]);
        else if(opt==9)printf("%lld\n",Catalan(a));
    }
}
第一类斯特林数 n^2递推 7.7.2 组合数学与计数
14 行
CPP JSON
【第一类斯特林数(n^2递推)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void get_stiring(Re N) — 获取值 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 13 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int s[N][N]; 
inline void get_stiring(Re N){
	for(Re i=0;i<=N;++i)s[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			s[j][i]=s[j-1][i-1]+(LL)(i-1)*s[j][i-1]%P;
}
int main(){}
第一类斯特林数·行 nlogn 优化倍增 NTT 7.7.2 组合数学与计数
75 行
CPP JSON
【第一类斯特林数·行(nlogn 优化倍增 NTT)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void xplus(Re *f,Re *F,Re n,Re c) — 核心算法函数 void sakura(Re *f,Re n) — 后缀数组 void get_Stirling(Re n) — 获取值 关键配置: N=262144+3,P=167772161,G=3 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 74 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=167772161,G=3;
int n,m,invn,invG,f[N],g[N],h[N],p[N],tr[N],jc[N],invjc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[i+len]%P;
				f[i+len]=(f[i]-tmp+P)%P,f[i]=(f[i]+tmp)%P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m){
	Re n_=n,m_=m;
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=n_+1;i<=n;++i)f[i]=0;
	for(Re i=m_+1;i<=n;++i)g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
inline void xplus(Re *f,Re *F,Re n,Re c){
	for(Re i=0;i<=n;++i)h[i]=(LL)F[i]*jc[i]%P;
	for(Re i=0,Mi=1;i<=n;++i)p[n-i]=(LL)Mi*invjc[i]%P,Mi=(LL)Mi*c%P;
	times(h,n,p,n);
	for(Re i=0;i<=n;++i)f[i]=(LL)h[n+i]*invjc[i]%P;
}
inline void sakura(Re *f,Re n){
	if(n==1){f[0]=0,f[1]=1;return;}//(x+0)
	if(n&1){
		sakura(f,n-1);
		for(Re i=n;i;--i)f[i]=((LL)f[i]*(n-1)%P+f[i-1])%P;
		f[0]=(LL)f[0]*(n-1)%P;
	}
	else sakura(f,n>>1),xplus(g,f,n>>1,n>>1),times(f,n>>1,g,n>>1);
}
int s[N];
inline void get_Stirling(Re n){
	invjc[1]=invjc[0]=jc[0]=1,invG=inv(G);
	if(n==0){s[0]=1;return;}
	for(Re i=1;i<=n;++i)jc[i]=(LL)jc[i-1]*i%P;
	for(Re i=2;i<=n;++i)invjc[i]=(LL)invjc[P%i]*(P-P/i)%P;
	for(Re i=2;i<=n;++i)invjc[i]=(LL)invjc[i]*invjc[i-1]%P;
	sakura(s,n);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),get_Stirling(n);
	for(Re i=0;i<=n;++i)printf("%d ",s[i]);
}
第一类斯特林数·行 nlog^2n 暴力分治 NTT 7.7.2 组合数学与计数
64 行
CPP JSON
【第一类斯特林数·行(nlog^2n 暴力分治 NTT)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void CDQ(Re L,Re R,Re deep) — 核心算法函数 void get_Stirling(Re n) — 获取值 关键配置: N=262144+3,P=167772161,G=3 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 63 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=167772161,G=3;
int n,m,invn,invG,tr[N],A[20][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[i+len]%P;
				f[i+len]=(f[i]-tmp+P)%P,f[i]=(f[i]+tmp)%P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m){
	Re n_=n,m_=m;
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=n_+1;i<=n;++i)f[i]=0;
	for(Re i=m_+1;i<=n;++i)g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
inline void CDQ(Re L,Re R,Re deep){
	if(L==R){A[deep][0]=L,A[deep][1]=1;return;}
	Re mid=L+R>>1;
	CDQ(L,mid,deep+1);
	for(Re i=0;i<=mid-L+1;++i)A[deep][i]=A[deep+1][i];
	CDQ(mid+1,R,deep+1);
	times(A[deep],mid-L+1,A[deep+1],R-mid);
}
int s[N];
inline void get_Stirling(Re n){
	invG=inv(G),CDQ(0,n-1,0);
	for(Re i=0;i<=n;++i)s[i]=A[0][i];
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),get_Stirling(n);
	for(Re i=0;i<=n;++i)printf("%d ",s[i]);
}
第二类斯特林数 n^2递推 7.7.2 组合数学与计数
14 行
CPP JSON
【第二类斯特林数(n^2递推)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void get_Stiring(Re N) — 获取值 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 13 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int S[N][N]; 
inline void get_Stiring(Re N){
	for(Re i=0;i<=N;++i)S[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			S[j][i]=S[j-1][i-1]+(LL)j*S[j][i-1]%P;
}
int main(){}
第二类斯特林数·行 NTT 7.7.2 组合数学与计数
54 行
CPP JSON
【第二类斯特林数·行(NTT)】 斯特林数(Stirling Number)模板,划分子集/排列的计数。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void sakura(Re *f,Re n,Re *g,Re m) — 后缀数组 void get_Stirling(Re n) — 获取值 关键配置: N=524288+3,P=167772161,G=3 说明:freopen("123.txt","r",stdin); 适用场景:计数问题、排列组合求值(含模运算)
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=524288+3,P=167772161,G=3;
int n,invG,f[N],g[N],tr[N],jc[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)f[i+len]*base%P;
				f[i+len]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int S[N];
inline void get_Stirling(Re n){
	jc[0]=1,invG=inv(G);
	for(Re i=1;i<=n;++i)jc[i]=(LL)jc[i-1]*i%P;
	for(Re i=0;i<=n;++i)f[i]=(LL)inv(jc[i])*((i&1)?P-1:1)%P,g[i]=(LL)mi(i,n)*inv(jc[i])%P;
	sakura(f,n,g,n);
	for(Re i=0;i<=n;++i)S[i]=f[i];
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),get_Stirling(n);
	for(Re i=0;i<=n;++i)printf("%d ",S[i]);
}
组合数 n^2记搜 7.7.2 组合数学与计数
13 行
CPP JSON
【组合数(n^2记搜)】 组合数学与计数模板。 核心函数: int C(Re m,Re n) — 核心算法函数 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 12 行 CPP
#include<cstdio>
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int C_[N][N]; 
inline int C(Re m,Re n){
    if(m>n)return 0;
    if(!m||m==n)return C_[m][n]=1;
    if(C_[m][n])return C_[m][n];
    return C_[m][n]=(C(m,n-1)+C(m-1,n-1))%P;
}
int main(){}
组合数 n^2递推 7.7.2 组合数学与计数
14 行
CPP JSON
【组合数(n^2递推)】 组合数学与计数模板。 核心函数: void get_C(Re N) — 获取值 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 13 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int C[N][N];
inline void get_C(Re N){
	for(Re i=0;i<=N;++i)C[0][i]=C[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			C[j][i]=(C[j-1][i-1]+C[j][i-1])%P;
}
int main(){}
贝尔数Bell n^2递推 7.7.2 组合数学与计数
32 行
CPP JSON
【贝尔数Bell(n^2递推)】 组合数学与计数模板。 核心函数: void get_C(Re N) — 获取值 void get_Bell(Re N) — 获取值 void get_Stiring(Re N) — 获取值 void get_Bell_(Re N) — 获取值 关键配置: N=1003,P=998244353 适用场景:计数问题、排列组合求值(含模运算)
C++ 31 行 CPP
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1003,P=998244353;
int B[N],C[N][N],S[N][N];
inline void get_C(Re N){
	for(Re i=0;i<=N;++i)C[0][i]=C[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			C[j][i]=(C[j-1][i-1]+C[j][i-1])%P;
}
inline void get_Bell(Re N){
	B[0]=1,get_C(N);
	for(Re i=1;i<=N;++i)
		for(Re j=0;j<=i-1;++j)
			(B[i]+=(LL)C[j][i-1]*B[j]%P)%=P;
}
inline void get_Stiring(Re N){
	for(Re i=0;i<=N;++i)S[i][i]=1;
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<i;++j)
			S[j][i]=S[j-1][i-1]+(LL)j*S[j][i-1]%P;
}
inline void get_Bell_(Re N){
	B[0]=1,get_Stiring(N);
	for(Re i=1;i<=N;++i)
		for(Re j=1;j<=i;++j)
			(B[i]+=S[j][i])%=P;
}
int main(){}
sg函数 sg 7.7.3 博弈论
56 行
CPP JSON
【sg函数(sg)】 SG 函数(Sprague-Grundy)模板,用于公平组合游戏的胜负判定。 核心函数: void get_sg(int n) — 获取值 关键配置: N=1e5 + 5 适用场景:公平组合游戏胜负判定、Nim-like 游戏分析
C++ 56 行 CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int sg[N], f[105], k; // f存允许的步数(需升序), k是步数种类
int vis[N];

void get_sg(int n) {
	for (int i = 1; i <= n; i++) {
		// vis时间戳黑科技:严格O(1)标记,绝对不写 memset
		for (int j = 1; j <= k && f[j] <= i; j++) {
			vis[sg[i - f[j]]] = i;
		}
		// 求 mex
		for (int j = 0; ; j++) {
			if (vis[j] != i) {
				sg[i] = j;
				break;
			}
		}
	}
}
int main() {
	// 1. 初始化规则数组 (必须升序!)
	k = 3;
	f[1] = 1; 
	f[2] = 3; 
	f[3] = 4;
	// sort(f + 1, f + 1 + k); // 如果题目给的规则没排序,一定要加上这句!
	
	// 2. 预处理 SG 函数
	// 假设题目告诉你,单堆石子最多 10000 个
	get_sg(10000); 
	
	// 3. 处理多堆石子的异或和
	int m;
	cin >> m; // m 堆石子
	
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		int a;
		cin >> a; // 读入这一堆有 a 个石子
		
		// 核心:把这一堆的 sg 值异或进去
		ans ^= sg[a]; 
	}
	
	// 4. 审判时刻
	if (ans != 0) {
		cout << "先手必胜!" << endl;
	} else {
		cout << "后手必胜!" << endl;
	}
	
	return 0;
}
对抗搜索+Alpha-Beta (一双木棋chess TLE) 最大分数 7.7.3 博弈论
54 行
CPP JSON
【对抗搜索+Alpha-Beta (一双木棋chess TLE)(最大分数)】 博弈论算法模板。 核心函数: void in(Re &x) — 核心算法函数 int findmin(Re alpha,Re op) — 查找(并查集寻根/二分查找) int findmax(Re beta,Re op) — 查找(并查集寻根/二分查找) 关键配置: N=13,inf=2e9 说明:freopen("123.txt","r",stdin); 适用场景:公平组合游戏胜负判定、Nim-like 游戏分析
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=13,inf=2e9;
int n,m,cnt,h[N],can[N],vis[N][N],A[2][N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int findmin(Re alpha,Re op);
inline int findmax(Re beta,Re op);
inline int findmin(Re alpha,Re op){
	if(cnt==n*m)return 0;
	Re ans=inf;
	for(Re i=1,j;i<=n;++i)
		if(h[i]<m&&vis[i][j=h[i]+1]==-1&&h[i-1]>=j){
			vis[i][j]=op,++cnt,++h[i];
			ans=min(ans,-A[op][i][j]+findmax(ans+A[op][i][j],op^1));
			vis[i][j]=-1,--cnt,--h[i];
			if(ans<=alpha)return ans;
		}
	return ans;
}
inline int findmax(Re beta,Re op){
	if(cnt==n*m)return 0;
	Re ans=-inf;
	for(Re i=1,j;i<=n;++i)
		if(h[i]<m&&vis[i][j=h[i]+1]==-1&&h[i-1]>=j){
			vis[i][j]=op,++cnt,++h[i];
			ans=max(ans,A[op][i][j]+findmin(ans-A[op][i][j],op^1));
			vis[i][j]=-1,--cnt,--h[i];
			if(ans>=beta)return ans;
		}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(A[1][i][j]);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(A[0][i][j]);
	memset(vis,-1,sizeof(vis));
	h[0]=inf; 
	printf("%d\n",findmax(inf,1));
}
对抗搜索+Alpha-Beta (Find the Winning Move) 胜负 7.7.3 博弈论
72 行
CPP JSON
【对抗搜索+Alpha-Beta (Find the Winning Move)(胜负)】 博弈论算法模板。 核心函数: void in(Re &x) — 核心算法函数 int check(Re op) — 判定/检查函数 int findmin(Re alpha,Re op) — 查找(并查集寻根/二分查找) int findmax(Re beta,Re op) — 查找(并查集寻根/二分查找) 关键配置: N=6,inf=2e9 适用场景:公平组合游戏胜负判定、Nim-like 游戏分析
C++ 71 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=6,inf=2e9;
int n=4,cnt,ansX,ansY,A[N][N];char op[5],s[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int check(Re op){
	for(Re i=1;i<=n;++i){
		Re cnt1=0,cnt2=0;
		for(Re j=1;j<=n;++j)cnt1+=(A[i][j]==op),cnt2+=(A[j][i]==op);
		if(cnt1==4||cnt2==4)return 1;
	}
	Re cnt1=0,cnt2=0;
	for(Re i=1;i<=n;++i)cnt1+=(A[i][i]==op),cnt2+=(A[i][n-i+1]==op);
	if(cnt1==4||cnt2==4)return 1;
	return 0;
}
inline int findmin(Re alpha,Re op);
inline int findmax(Re beta,Re op);//[op=1:�ҵĻغ�]
inline int findmin(Re alpha,Re op){
	if(cnt==16)return 0;
	if(check(op^1))return inf;
	Re ans=inf;
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=n;++j)
			if(A[i][j]==-1){
				A[i][j]=op,++cnt;
				ans=min(ans,findmax(ans,op^1));
				A[i][j]=-1,--cnt;
				if(ans<=alpha)return ans;
			}
	return ans;
}
inline int findmax(Re beta,Re op){
	if(cnt==16)return 0;
	if(check(op^1))return -inf;
	Re ans=-inf;
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=n;++j)
			if(A[i][j]==-1){
				A[i][j]=op,++cnt;
				ans=max(ans,findmin(ans,op^1));
				A[i][j]=-1,--cnt;
				ansX=i,ansY=j;
				if(ans>=beta)return ans;
			}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	while(~scanf("%s",op)&&op[0]!='$'){
		cnt=0;
		for(Re i=1;i<=n;++i){
			scanf("%s",s+1);
			for(Re j=1;j<=n;++j)
				if(s[j]=='.')A[i][j]=-1,++cnt;
				else A[i][j]=(s[j]=='x');
		}
		if(cnt<=4)puts("#####");
		else if(findmax(inf,1)==inf)printf("(%d,%d)\n",ansX-1,ansY-1);
		else puts("#####");
	}
}
对抗搜索+记忆化 (一双木棋chess) 最大分数 7.7.3 博弈论
45 行
CPP JSON
【对抗搜索+记忆化 (一双木棋chess)(最大分数)】 博弈论算法模板。 核心函数: void in(Re &x) — 核心算法函数 LL Hash(Re op) — 哈希计算 int dfs(Re op) — 深度优先搜索遍历 关键配置: N=13,inf=2e9 说明:freopen("123.txt","r",stdin); 适用场景:公平组合游戏胜负判定、Nim-like 游戏分析
C++ 44 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=13,inf=2e9;
int n,m,cnt,h[N],can[N],vis[N][N],A[2][N][N];
map<LL,int>pan;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LL Hash(Re op){LL ans=op+1;for(Re i=1;i<=n;++i)ans=ans*11ll+h[i];return ans;}
inline int dfs(Re op){
	if(cnt==n*m)return 0;
	LL H=Hash(op);
	if(pan.find(H)!=pan.end())return pan[H];
	Re ans=op?-inf:inf;
	for(Re i=1,j;i<=n;++i)
		if(h[i]<m&&vis[i][j=h[i]+1]==-1&&h[i-1]>=j){
			vis[i][j]=op,++cnt,++h[i];
			if(op)ans=max(ans,dfs(op^1)+A[op][i][j]);
			else ans=min(ans,dfs(op^1)-A[op][i][j]);
			vis[i][j]=-1,--cnt,--h[i];
		}
	return pan[H]=ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(A[1][i][j]);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(A[0][i][j]);
	memset(vis,-1,sizeof(vis));
	h[0]=inf;
	printf("%d\n",dfs(1));
}
多项式乘法-快速傅里叶变换 FFT 7.7.4 多项式与FFT
85 行
CPP JSON
【快速傅里叶变换(FFT)——多项式乘法】 ▪ Complex — 复数结构体,支持 +、-、* 运算符重载(复数运算) ▪ getSize(n) — 计算 ≥n 的最小 2 的幂作为变换长度 ▪ change(a, n) — 位逆序重排(bit-reversal permutation),将系数数组重排为蝴蝶变换所需顺序 ▪ fft(a, n, opt) — 快速傅里叶变换核心:opt=1 正变换,opt=-1 逆变换;Cooley–Tukey 迭代算法,每层蝴蝶变换 O(N),共 log N 层 两个 n 次多项式乘法从 O(N²) 优化到 O(N log N)。适用于大整数乘法、生成函数卷积、信号处理。
C++ 85 行 CPP
struct Polynoial{
    struct Complex{
        double x,y;
        Complex(double _x = 0.0,double _y = 0.0){
            x = _x;
            y = _y;
        }
        Complex operator-(const Complex &rhs) const{
            return Complex(x-rhs.x,y-rhs.y);
        }
        Complex operator+(const Complex &rhs) const{
            return Complex(x+rhs.x,y+rhs.y);
        }
        Complex operator*(const Complex &rhs) const{
            return Complex(x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x);
        }
    };
    
    int getSize(int n) {
        int size = 1;
        while (size < n) size <<= 1;
        return size;
    }
    
    void change(vector<Complex>&a,int n){
        for(int i = 1,j = n/2;i < n-1;i++){
            if(i < j){
                swap(a[i],a[j]);
            }
            int k = n/2;
            while(j >= k){
                j -= k;
                k /= 2;
            }
            if(j < k)j += k;
        }
    }
    
    void fft(vector<Complex>&a,int n,int opt){
        change(a,n);
        for(int h = 2;h <= n;h*=2){
            Complex wn(cos(2*PI/h),sin(opt*2*PI/h));  // 修正:PI/h 而不是 PI/n
            for(int j = 0;j < n;j+=h){
                Complex w(1,0);
                for(int k = j;k < j+h/2;k++){
                    Complex u = a[k];
                    Complex t = w*a[k+h/2];
                    a[k]=u+t;
                    a[k+h/2]=u-t;
                    w=w*wn;
                }
            }
        }
        if(opt == -1){
            for(int i = 0;i < n;i++){
                a[i].x /= n;
            }
        }
    }

    vector<int> multiply(vector<int>& a, vector<int>& b) {
        int size = getSize(a.size() + b.size() - 1);
        
        vector<Complex> fa(size), fb(size);
        for(int i = 0; i < (int)a.size(); i++) fa[i] = Complex(a[i], 0);
        for(int i = 0; i < (int)b.size(); i++) fb[i] = Complex(b[i], 0);
        for(int i = a.size(); i < size; i++) fa[i] = Complex(0, 0);
        for(int i = b.size(); i < size; i++) fb[i] = Complex(0, 0);
        
        fft(fa, size, 1);
        fft(fb, size, 1);
        
        for(int i = 0; i < size; i++) {
            fa[i] = fa[i] * fb[i];
        }
        
        fft(fa, size, -1);
        
        vector<int> res(size);
        for(int i = 0; i < size; i++) {
            res[i] = (int)(fa[i].x + 0.5);
        }
        return res;
    }
};
Perpetual Subtraction 生成函数 移位 7.7.4 多项式与FFT
65 行
CPP JSON
【Perpetual Subtraction(生成函数 移位)】 多项式算法模板。 核心函数: template<typename T>inline void in(T &x) — 核心算法函数 int mi(Re x,LL k) — 核心算法函数 int Inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 关键配置: N=262144+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin);;for(Re i=0;i<=n;++i)printf("%d ",g0[i]);puts("");;for(Re i=0;i<=n;++i)printf("%d ",gm[i]);puts(""); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 64 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,invn,invG,f[N],g[N],g0[N],gm[N],f0[N],fm[N],tr[N],jc[N],inv[N],invjc[N];LL m;
template<typename T>inline void in(T &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,LL k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int Inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[len+i]%P;
				f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
	}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);invn=Inv(n),invG=Inv(G);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//    freopen("123.txt","r",stdin);
    in(n),in(m);
    for(Re i=0;i<=n;++i)in(f0[i]);
    invjc[1]=invjc[0]=inv[1]=jc[1]=jc[0]=1;
    for(Re i=2;i<=n+1;++i)inv[i]=(LL)inv[P%i]*(P-P/i)%P,jc[i]=(LL)jc[i-1]*i%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P;
    
	for(Re i=0;i<=n;++i)f[i]=(LL)jc[n-i]*f0[n-i]%P,g[i]=invjc[i];
    times(f,n,g,n);
	for(Re i=0;i<=n;++i)g0[i]=(LL)f[n-i]*invjc[i]%P;
	
//	for(Re i=0;i<=n;++i)printf("%d ",g0[i]);puts("");
	for(Re i=0;i<=n;++i)gm[i]=(LL)g0[i]*mi(inv[i+1],m)%P;
//	for(Re i=0;i<=n;++i)printf("%d ",gm[i]);puts("");

	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(Re i=0;i<=n;++i)f[i]=(LL)jc[n-i]*gm[n-i]%P,g[i]=(LL)invjc[i]*((i&1)?P-1:1)%P;
	times(f,n,g,n);
	for(Re i=0;i<=n;++i)fm[i]=(LL)f[n-i]*invjc[i]%P;
	
	for(Re i=0;i<=n;++i)printf("%d ",fm[i]);
}
A×B Problem FFT 7.7.4 多项式与FFT
58 行
CPP JSON
【A×B Problem(FFT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 void FFT(CP *f,Re n,Re op) — 快速傅里叶变换 核心结构体:CP 关键配置: N=2097152+5 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 57 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+5;
const LD Pi=acos(-1);
int n,m,tr[N],Ans[N];char s1[N>>1],s2[N>>1];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct CP{
	LD x,y;
	CP(LD X=0,LD Y=0){x=X,y=Y;}
	inline CP operator+(const CP &O)const{return CP(x+O.x,y+O.y);}
	inline CP operator-(const CP &O)const{return CP(x-O.x,y-O.y);}
	inline CP operator*(const CP &O)const{return CP(x*O.x-y*O.y,x*O.y+y*O.x);}
	inline CP operator*=(const CP &O){return *this=*this*O;}
}f[N],g[N];
inline void FFT(CP *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1;
		CP w1(cos(2*Pi/p),sin(2*Pi/p));
		if(op)w1.y*=-1;
		for(Re st=0;st<n;st+=p){
			CP base(1,0);
			for(Re i=st;i<=st+len-1;++i){
				CP tmp=f[len+i]*base;
				f[len+i]=f[i]-tmp,f[i]=f[i]+tmp,base*=w1;
			}
		}
	}
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%s%s",s1,s2),n=strlen(s1),m=strlen(s2);
	for(Re i=0;i<n;++i)f[i].x=s1[n-i-1]-'0';
	for(Re i=0;i<m;++i)g[i].x=s2[m-i-1]-'0';
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	FFT(f,n,0),FFT(g,n,0);
	for(Re i=0;i<n;++i)f[i]*=g[i];
	FFT(f,n,1);
	for(Re i=0;i<=m;++i){
		Ans[i]+=(int)(f[i].x/n+0.5);
		if(Ans[i]>9)Ans[i+1]+=Ans[i]/10,Ans[i]%=10,m+=(i==m);
	}
	while(!Ans[m]&&m>=1)--m;
	for(Re i=m;i>=0;--i)printf("%d",Ans[i]);
}
分治NTT 循环卷积优化 7.7.4 多项式与FFT
65 行
CPP JSON
【分治NTT(循环卷积优化)】 数论变换(NTT)模板,在模意义下计算多项式卷积,避免浮点误差。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void CDQ(Re L,Re R) — 核心算法函数 关键配置: N=131072+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 64 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=131072+3,P=998244353,G=3;
int n,m,invn,invG,f[N],g[N],A[N],tr[N],ans[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[i+len]%P;
				f[i+len]=(f[i]-tmp+P)%P;
				f[i]=(f[i]+tmp)%P;
				base=(LL)base*w1%P;
			}
	}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(n=1;n<=m;n<<=1);
	for(Re i=m+1;i<=n;++i)f[i]=g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0,invn=inv(n);i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
inline void CDQ(Re L,Re R){
	if(L==R)return;
	Re mid=L+R>>1;CDQ(L,mid);
	for(Re i=L;i<=R;++i)g[i-L]=A[i-L];
	for(Re i=L;i<=mid;++i)f[i-L]=ans[i];
	for(Re i=mid+1;i<=R;++i)f[i-L]=0;
	times(f,mid-L,g,R-L);
	for(Re i=mid+1;i<=R;++i)(ans[i]+=f[i-L])%=P;
	CDQ(mid+1,R);
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),invG=inv(G);
	for(Re i=1;i<n;++i)in(A[i]);
	ans[0]=1,CDQ(0,n-1);
	for(Re i=0;i<n;++i)printf("%d ",ans[i]);
}
多项式 乘法 FFT 7.7.4 多项式与FFT
58 行
CPP JSON
【多项式 乘法(FFT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 void FFT(CP *f,Re n,Re op) — 快速傅里叶变换 void times(CP *f,Re n,CP *g,Re m) — 核心算法函数 核心结构体:CP 关键配置: N=2097152+3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 57 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+3;
const LD Pi=acos(-1);
int n,m,tr[N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
struct CP{
	LD x,y;CP(LD X=0,LD Y=0){x=X,y=Y;}
	inline CP operator+(const CP &O)const{return CP(x+O.x,y+O.y);}
	inline CP operator-(const CP &O)const{return CP(x-O.x,y-O.y);}
	inline CP operator*(const CP &O)const{return CP(x*O.x-y*O.y,x*O.y+y*O.x);}//(ac-bd,bc+ad)
	inline CP operator/(const CP &O)const{
		LD tmp=O.x*O.x+O.y*O.y;//tmp=c^2+d^2
		return CP((x*O.x+y*O.y)/tmp,(y*O.x-x*O.y)/tmp);//( (ac+bd)/tmp,(bc-ad)/tmp )
	}
	inline CP operator*=(const CP &O){return *this=*this*O;}
}f[N],g[N];
inline void FFT(CP *f,Re n,Re op){//op=0:DFT, op=1:IDFT
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1;CP w1(cos(2*Pi/p),sin(2*Pi/p));
		if(op)w1.y*=-1;
		for(Re st=0;st<n;st+=p){
			CP base(1,0);
			for(Re i=st;i<=st+len-1;++i){
				CP tmp=base*f[len+i];
				f[len+i]=f[i]-tmp,f[i]=f[i]+tmp,base*=w1;
			}
		}
	}
}
inline void times(CP *f,Re n,CP *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	FFT(f,n,0),FFT(g,n,0);
	for(Re i=0;i<n;++i)f[i]*=g[i];
	FFT(f,n,1);
	for(Re i=0;i<=m;++i)f[i].x/=n;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=0;i<=n;++i)scanf("%lf",&f[i].x);
	for(Re i=0;i<=m;++i)scanf("%lf",&g[i].x);
	times(f,n,g,m);
	for(Re i=0;i<=n+m;++i)printf("%d ",(int)(f[i].x+0.5));
}
多项式 乘法 NTT 7.7.4 多项式与FFT
51 行
CPP JSON
【多项式 乘法(NTT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 关键配置: N=2097152+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 50 行 CPP
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=2097152+3,P=998244353,G=3;
int n,m,invn,invG,f[N],g[N],tr[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[len+i]%P;
				f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
	}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);invn=inv(n),invG=inv(G);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=0;i<=n;++i)in(f[i]);
	for(Re i=0;i<=m;++i)in(g[i]);
	times(f,n,g,m);
	for(Re i=0;i<=n+m;++i)printf("%d ",f[i]);
}
多项式 位运算卷积 FWT 7.7.4 多项式与FFT
52 行
CPP JSON
【多项式 位运算卷积(FWT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int inv(Re x) — 求模逆元 void FWT(Re *f,Re n,Re op) — 核心算法函数 void sakura(Re *A,Re *B,Re n,Re id_) — 后缀数组 关键配置: N=131072+3,P=998244353 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 51 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=131072+3,P=998244353;
int n,m,inv2,A[N],B[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int inv(Re x){
	Re s=1,k=P-2;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
int id,f[N],g[N];
inline void FWT(Re *f,Re n,Re op){
	for(Re p=2;p<=n;p<<=1)
		for(Re st=1,len=p>>1;st<n;st+=p)
			for(Re j=st;j<=st+len-1;++j)
				if(id==1)(f[j+len]+=(op?P-f[j]:f[j]))%=P;
				else if(id==2)(f[j]+=(op?P-f[j+len]:f[j+len]))%=P;
				else{
					Re g0=f[j],g1=f[j+len];
					f[j]=(g0+g1)%P,f[j+len]=(g0-g1+P)%P;
					if(op)f[j]=(LL)f[j]*inv2%P,f[j+len]=(LL)f[j+len]*inv2%P;
				}
}
inline void sakura(Re *A,Re *B,Re n,Re id_){
	for(Re i=1;i<=n;++i)f[i]=A[i],g[i]=B[i];id=id_;
	FWT(f,n,0),FWT(g,n,0);
	for(Re i=1;i<=n;++i)f[i]=(LL)f[i]*g[i]%P;
	FWT(f,n,1);
	for(Re i=1;i<=n;++i)printf("%d ",f[i]);puts("");
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),n=(1<<n),inv2=inv(2);
	for(Re i=1;i<=n;++i)in(A[i]);
	for(Re i=1;i<=n;++i)in(B[i]);
	sakura(A,B,n,1),sakura(A,B,n,2),sakura(A,B,n,3);
}
多项式 快速幂 nlog^2n 暴力 7.7.4 多项式与FFT
67 行
CPP JSON
【多项式 快速幂(nlog^2n 暴力)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int in_(无参数) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void polymi(Re *x,Re n,Re k,Re *s) — 核心算法函数 关键配置: N=262144+3,P=998244353,G=3,phi=P-1 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 66 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int 
using namespace std;
const int N=262144+3,P=998244353,G=3,phi=P-1;
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
inline int in_(){
	int f=0;LL x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+(ch^48),x%=P,ch=getchar();
	return x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
	for(Re i=1;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)f[i+len]*base%P;
				f[i+len]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m){
	Re n_=n,m_=m;
	for(m+=n,n=1;n<=m;n<<=1);invG=inv(G);
	for(Re i=n_+1;i<n;++i)f[i]=0;
	for(Re i=m_+1;i<n;++i)g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);Re invn=inv(n);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int c[N];
inline void polymi(Re *x,Re n,Re k,Re *s){
	k%=P,s[0]=1;
	for(Re i=1;i<=n;++i)s[i]=0;
	while(k){
		if(k&1){for(Re i=0;i<=n;++i)c[i]=x[i];times(s,n,c,n);}
		for(Re i=0;i<=n;++i)c[i]=x[i];times(x,n,c,n),k>>=1;
	}
}
int n,K,f[N],g[N];
int main(){
//	freopen("123.txt","r",stdin);
	in(n),--n,K=in_();
	for(Re i=0;i<=n;++i)in(f[i]);
	polymi(f,n,K,g);
	for(Re i=0;i<=n;++i)printf("%d ",g[i]);
}
多项式 求逆 nlogn 优化倍增 NTT 7.7.4 多项式与FFT
59 行
CPP JSON
【多项式 求逆(nlogn 优化倍增 NTT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m,Re op=0) — 核心算法函数 void polyinv(Re *a,Re n,Re *b) — 求模逆元 关键配置: N=262144+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 58 行 CPP
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,A[N],B[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m,Re op=0){
	Re n_=n,m_=m;
	for(m+=n,n=1;n<=m;n<<=1);invG=inv(G);
	for(Re i=n_+1;i<n;++i)f[i]=0;
	for(Re i=m_+1;i<n;++i)g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P*(op?g[i]:1)%P;
	NTT(f,n,1);Re invn=inv(n);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int f[N],g[N];
inline void polyinv(Re *a,Re n,Re *b){
	if(n==0){b[0]=inv(a[0]);return;}
	polyinv(a,n>>1,b);
	for(Re i=0;i<=n;++i)f[i]=a[i],g[i]=b[i];
	times(f,n,g,n,1);
	for(Re i=0;i<=n;++i)b[i]=(2*b[i]%P-f[i]+P)%P;
}
int main(){
//    freopen("123.txt","r",stdin);
	in(n),--n;
	for(Re i=0;i<=n;++i)in(A[i]),A[i]%=P;
	polyinv(A,n,B);
	for(Re i=0;i<=n;++i)printf("%d ",B[i]);
}
多项式 求逆 nlog^2n 暴力分治 FFT 7.7.4 多项式与FFT
66 行
CPP JSON
【多项式 求逆(nlog^2n 暴力分治 FFT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 void CDQ(Re L,Re R) — 核心算法函数 void polyinv(Re *a,Re n,Re *b) — 求模逆元 关键配置: N=262144+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 65 行 CPP
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,A[N],B[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1)
		for(Re st=0,len=p>>1,w1=mi(op?invG:G,(P-1)/p);st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P,base=(LL)base*w1%P;
			}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(n=1;n<=m;n<<=1);invG=inv(G);
	for(Re i=m+1;i<n;++i)f[i]=g[i]=0;
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);Re invn=inv(n);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int f[N],g[N],c[N],ans[N];
inline void CDQ(Re L,Re R){
	if(L==R)return;
	Re mid=L+R>>1;CDQ(L,mid);
	for(Re i=L;i<=R;++i)g[i-L]=c[i-L];
	for(Re i=L;i<=mid;++i)f[i-L]=ans[i];
	for(Re i=mid+1;i<=R;++i)f[i-L]=0;
	times(f,mid-L,g,R-L);
	for(Re i=mid+1;i<=R;++i)(ans[i]+=f[i-L])%=P;
	CDQ(mid+1,R);
}
inline void polyinv(Re *a,Re n,Re *b){
	Re tmp=inv(a[0]);c[0]=0;
	for(Re i=1;i<=n;++i)c[i]=(LL)(P-a[i])*tmp%P;
	ans[0]=tmp,CDQ(0,n);
	for(Re i=0;i<=n;++i)b[i]=ans[i];
}
int main(){
//    freopen("123.txt","r",stdin);
	in(n),--n;
	for(Re i=0;i<=n;++i)in(A[i]),A[i]%=P;
	polyinv(A,n,B);
	for(Re i=0;i<=n;++i)printf("%d ",B[i]);
}
字符串匹配 NTT 7.7.4 多项式与FFT
63 行
CPP JSON
【字符串匹配(NTT)】 多项式算法模板。 核心函数: void in(Re &x) — 核心算法函数 void get_next(无参数) — 获取值 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void sakura(Re *f,Re n,Re *g,Re m) — 后缀数组 关键配置: N=1048576+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=1048576+3,P=998244353,G=3;
int n,m,ans,invG,f[N],g[N],tr[N],S1[N],S2[N],PA[N],nex[N];char A[N],B[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline void get_next(){
	for(Re i=2,j=0;i<=m;++i){
		while(j&&B[i]!=B[j+1])j=nex[j];
		if(B[i]==B[j+1])++j;nex[i]=j;
	}
	for(Re i=1;i<=m;++i)printf("%d ",nex[i]);
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
				base=(LL)base*w1%P;
			}
	}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
	for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	scanf("%s%s",A+1,B+1),invG=inv(G);
	n=strlen(A+1),m=strlen(B+1);
	for(Re i=1;i<=n;++i)f[i]=A[n-i+1]-'A'+1,S1[i]=S1[i-1]+f[i]*f[i];
	for(Re i=1;i<=m;++i)g[i]=B[i]-'A'+1,S2[i]=S2[i-1]+g[i]*g[i];
	sakura(f,n,g,m);
	for(Re i=m;i<=n;++i)PA[n-i+1]=((S1[i]-S1[i-m]+S2[m])%P-2*f[i+1]%P+P)%P;
	for(Re i=1;i<=n-m+1;++i)if(PA[i]==0)printf("%d\n",i);
	get_next();
}
拉格朗日插值 x从0到n不连续 7.7.4 多项式与FFT
54 行
CPP JSON
【拉格朗日插值(x从0到n不连续)】 拉格朗日插值法模板,通过 n+1 个点确定 n 次多项式。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int Inv(Re x) — 求模逆元 void mul(Re *f,Re n,Re a0,Re *g) — 核心算法函数 void div(Re *g,Re n,Re a0,Re *f) — 核心算法函数 void Lagrange(Re *x,Re *y,Re n,Re *F) — 核心算法函数 关键配置: N=2003+3,P=998244353 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2003+3,P=998244353;
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int Inv(Re x){return mi(x,P-2);}
int ff[N],gg[N];
inline void mul(Re *f,Re n,Re a0,Re *g){
	for(Re i=0;i<=n;++i)ff[i]=f[i];
	g[0]=(LL)a0*ff[0]%P;for(Re i=1;i<=n+1;++i)g[i]=((LL)a0*ff[i]%P+ff[i-1])%P;
}
inline void div(Re *g,Re n,Re a0,Re *f){
	for(Re i=0;i<=n;++i)gg[i]=g[i];
	f[n-1]=gg[n];for(Re i=n-2;i>=0;--i)f[i]=(gg[i+1]-(LL)a0*f[i+1]%P+P)%P;
}
int fi[N],fmul[N];
inline void Lagrange(Re *x,Re *y,Re n,Re *F){
	fmul[0]=P-x[0],fmul[1]=1;
	for(Re i=1;i<=n;++i)mul(fmul,i,P-x[i],fmul);
	for(Re i=0;i<=n-1;++i)F[i]=0;
	for(Re i=0;i<=n;++i){
		Re tmp=1;
		for(Re j=0;j<=n;++j)if(i!=j)tmp=(LL)tmp*(x[i]-x[j]+P)%P;
		tmp=(LL)y[i]*Inv(tmp)%P;
		div(fmul,n+1,P-x[i],fi);
		for(Re i=0;i<=n;++i)(F[i]+=(LL)tmp*fi[i]%P)%=P;
	}
}
int n,X,ans,x[N],y[N],F[N];
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(X),--n;
	for(Re i=0;i<=n;++i)in(x[i]),in(y[i]);
	Lagrange(x,y,n,F);
	for(Re i=0,tmp=1;i<=n;++i)(ans+=(LL)F[i]*tmp%P)%=P,tmp=(LL)tmp*X%P;
	printf("%d\n",ans);
}
拉格朗日插值 x从0到n连续 7.7.4 多项式与FFT
56 行
CPP JSON
【拉格朗日插值(x从0到n连续)】 拉格朗日插值法模板,通过 n+1 个点确定 n 次多项式。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int Inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void times(Re *f,Re n,Re *g,Re m) — 核心算法函数 关键配置: N=1048576+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 55 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=1048576+3,P=998244353,G=3;
int jc[N],inv[N],invjc[N];
inline void in(Re &x){
	int f=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int Inv(Re x){return mi(x,P-2);}
int invG,tr[N];
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re i=st,base=1;i<=st+len-1;++i){
				Re tmp=(LL)base*f[len+i]%P;
				f[len+i]=(f[i]-tmp+P)%P,(f[i]+=tmp)%=P,base=(LL)base*w1%P;
			}
	}
}
inline void times(Re *f,Re n,Re *g,Re m){
	for(m+=n,n=1;n<=m;n<<=1);invG=Inv(G);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);Re invn=Inv(n);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int n,m,y[N],f[N],g[N],F[N];
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),jc[0]=jc[1]=inv[1]=invjc[0]=invjc[1]=1;
	for(Re i=2;i<=n;++i)inv[i]=(LL)inv[P%i]*(P-P/i)%P,jc[i]=(LL)jc[i-1]*i%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P;
	for(Re i=0;i<=n;++i)in(y[i]),g[i]=(LL)y[i]*((n-i&1)?P-1:1)%P*invjc[i]%P*invjc[n-i]%P;
	for(Re i=0;i<=(n<<1);++i)f[i]=Inv(m-n+i);
	times(f,n<<1,g,n);Re tmp=1;
	for(Re i=m-n;i<=m;++i)tmp=(LL)tmp*i%P;
	for(Re i=0;i<=n;tmp=(LL)tmp*Inv(m-n+i)%P,++i,tmp=(LL)tmp*(m+i)%P)F[i]=(LL)tmp*f[n+i]%P;
	for(Re i=m;i<=m+n;++i)printf("%d ",F[i-m]);
}
字符串匹配套路一:通配符 (NTT) 残缺的字符串 7.7.4 多项式与FFT
70 行
CPP JSON
【字符串匹配套路一:通配符 (NTT)(残缺的字符串)】 数论变换(NTT)模板,在模意义下计算多项式卷积,避免浮点误差。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void sakura(Re *f,Re n,Re *g,Re m) — 后缀数组 关键配置: N=524288+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 69 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=524288+3,P=998244353,G=3;
int n,m,ans,invG,a[N],b[N],f[N],g[N],tr[N],PA[N];char A[N],B[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
				base=(LL)base*w1%P;
			}
	}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
	for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(m),in(n),scanf("%s%s",B+1,A+1),invG=inv(G);
	for(Re i=1;i<=n/2;++i)swap(A[i],A[n-i+1]);
	for(Re i=1;i<=n;++i)a[i]=(A[i]=='*'?0:A[i]-'a'+1);
	for(Re i=1;i<=m;++i)b[i]=(B[i]=='*'?0:B[i]-'a'+1);
	for(Re i=1;i<=n;++i)f[i]=(LL)a[i]*a[i]%P*a[i]%P;
	for(Re i=1;i<=m;++i)g[i]=b[i];
	sakura(f,n,g,m);
	for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(Re i=1;i<=n;++i)f[i]=a[i];
	for(Re i=1;i<=m;++i)g[i]=(LL)b[i]*b[i]%P*b[i]%P;
	sakura(f,n,g,m);
	for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(Re i=1;i<=n;++i)f[i]=(LL)a[i]*a[i]%P;
	for(Re i=1;i<=m;++i)g[i]=(LL)b[i]*b[i]%P;
	sakura(f,n,g,m);
	for(Re i=m;i<=n;++i)(PA[n-i+1]+=P-2*f[i+1]%P)%=P;
	Re ans=0;
	for(Re i=1;i<=n-m+1;++i)ans+=(PA[i]==0);
	printf("%d\n",ans);
	for(Re i=1;i<=n-m+1;++i)if(PA[i]==0)printf("%d ",i);
}
字符串匹配套路二:较小字符集 (NTT) Fuzzy Search 7.7.4 多项式与FFT
63 行
CPP JSON
【字符串匹配套路二:较小字符集 (NTT)(Fuzzy Search)】 数论变换(NTT)模板,在模意义下计算多项式卷积,避免浮点误差。 核心函数: void in(Re &x) — 核心算法函数 int mi(Re x,Re k) — 核心算法函数 int inv(Re x) — 求模逆元 void NTT(Re *f,Re n,Re op) — 数论变换 void sakura(Re *f,Re n,Re *g,Re m) — 后缀数组 关键配置: N=262144+3,P=998244353,G=3 复杂度:O(N log N) 说明:freopen("123.txt","r",stdin); 适用场景:多项式卷积(大整数乘法、生成函数计算)、信号处理
C++ 62 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define Re register int
#define LL long long
using namespace std;
const int N=262144+3,P=998244353,G=3;
int n,m,K,invG,a[N],b[N],f[N],g[N],S[N],tr[N],PA[N],id[200];char A[N],B[N];
inline void in(Re &x){
    int fu=0;x=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int mi(Re x,Re k){
	Re s=1;
	while(k){
		if(k&1)s=(LL)s*x%P;
		x=(LL)x*x%P,k>>=1;
	}
	return s;
}
inline int inv(Re x){return mi(x,P-2);}
inline void NTT(Re *f,Re n,Re op){
	for(Re i=0;i<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);
	for(Re p=2;p<=n;p<<=1){
		Re len=p>>1,w1=mi(op?invG:G,(P-1)/p);
		for(Re st=0;st<n;st+=p)
			for(Re j=st,base=1;j<=st+len-1;++j){
				Re tmp=(LL)base*f[j+len]%P;
				f[j+len]=(f[j]-tmp+P)%P,(f[j]+=tmp)%=P;
				base=(LL)base*w1%P;
			}
	}
}
inline void sakura(Re *f,Re n,Re *g,Re m){
	for(m=n+1,n=1;n<=m;n<<=1);Re invn=inv(n);
	for(Re i=1;i<n;++i)tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	NTT(f,n,0),NTT(g,n,0);
	for(Re i=0;i<n;++i)f[i]=(LL)f[i]*g[i]%P;
	NTT(f,n,1);
	for(Re i=0;i<=m;++i)f[i]=(LL)f[i]*invn%P;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),in(K),scanf("%s%s",A+1,B+1),invG=inv(G);
	id['A']=1,id['T']=2,id['C']=3,id['G']=4;
	for(Re i=1;i<=n;++i)a[i]=id[A[n-i+1]];
	for(Re i=1;i<=m;++i)b[i]=id[B[i]];
	for(Re o=1;o<=4;++o){
		for(Re i=1;i<=n;++i)S[i]=S[i-1]+(a[i]==o);
		for(Re i=1;i<=n;++i)f[i]=(S[i]-S[max(i-K-1,0)]||S[min(i+K,n)]-S[i-1]);
		for(Re i=1;i<=m;++i)g[i]=(b[i]==o);
		sakura(f,n,g,m);
		for(Re i=m;i<=n;++i)(PA[n-i+1]+=f[i+1])%=P;
		memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	}
	Re ans=0;
	for(Re i=1;i<=n-m+1;++i)ans+=(PA[i]==m);
	printf("%d\n",ans);
}
19 行
CPP JSON
【高斯消元法——解线性方程组(实系数)】 ▪ Gauss(a, n) — 对 n×(n+1) 的增广矩阵 a 做高斯消元: ① 列主元选取:每列找绝对值最大的行 r 作为主元行,提高数值稳定性 ② 消元:用第 i 行消去下方所有行第 i 列(a[j][k] -= t*a[i][k]) ③ 回代:从第 n 行向上,依次解出每个未知数 时间复杂度 O(N³)。含 eps 判零处理。适用于 n 元线性方程组、矩阵求逆、行列式计算。
C++ 19 行 CPP
bool Gauss(Matrix a, int n) {
    for(int i=1; i<=n; i++) {
        int r=i;
        for(int j=i+1; j<=n; j++) 
            if(abs(a[j][i]) > abs(a[r][i])) r=j;
        if(abs(a[r][i])<eps) return false;
        if(r!=i) for(int j=1; j<=n+1; j++) swap(a[r][j], a[i][j]);
        
        for(int j=i+1; j<=n; j++) {
            double t = a[j][i]/a[i][i];
            for(int k=i; k<=n+1; k++) a[j][k] -= t*a[i][k];
        }
    }
    for(int i=n; i>=1; i--) {
        for(int j=n; j>i; j--) a[i][n+1] -= a[i][j]*a[j][n+1];
        a[i][n+1] /= a[i][i];
    }
    return true;
}
高斯消元-解加法方程组 gauss-add 7.7.5 线性代数与高斯消元
19 行
CPP JSON
【高斯消元——解异或(加法)方程组(GF(2) 域)】 ▪ Gauss(a, n) — 对 n×(n+1) 的增广矩阵在 GF(2) 域上做高斯消元: ① 列主元选取(找第 i 列绝对值最大的行) ② 消元(前向消去下方行) ③ 回代(从下往上解出各变量) 与 ID=11 的 Gauss 算法结构相同,但使用按位异或(^)替代加减法,在 GF(2) 域上操作。 时间复杂度 O(N³)。适用于解 XOR 方程组、开关灯问题、线性基构建等。
C++ 19 行 CPP
bool Gauss(Matrix a, int n) {
	for(int i=1; i<=n; i++) {
		int r=i;
		for(int j=i+1; j<=n; j++) 
			if(abs(a[j][i]) > abs(a[r][i])) r=j;
		if(abs(a[r][i])<eps) return false;
		if(r!=i) for(int j=1; j<=n+1; j++) swap(a[r][j], a[i][j]);
		
		for(int j=i+1; j<=n; j++) {
			double t = a[j][i]/a[i][i];
			for(int k=i; k<=n+1; k++) a[j][k] -= t*a[i][k];
		}
	}
	for(int i=n; i>=1; i--) {
		for(int j=n; j>i; j--) a[i][n+1] -= a[i][j]*a[j][n+1];
		a[i][n+1] /= a[i][i];
	}
	return true;
}
前缀线性基 Ivan and Burgers 7.7.5 线性代数与高斯消元
40 行
CPP JSON
【前缀线性基(Ivan and Burgers)】 线性代数模板。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re x,Re id) — 插入元素 int ask(Re L) — 核心算法函数 核心结构体:JI 关键配置: N=5e5+3,logN=20,inf=2e9 说明:freopen("456.txt","r",stdin);
C++ 39 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=5e5+3,logN=20,inf=2e9;
int n,x,y,T;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct JI{
	int p[logN+1],ip[logN+1];JI(){memset(p,0,sizeof(p));}
	inline void insert(Re x,Re id){
		for(Re i=logN;i>=0;--i)
			if((x>>i)&1){
				if(!p[i]){p[i]=x,ip[i]=id;break;}
				if(ip[i]<id)swap(p[i],x),swap(ip[i],id);
				x^=p[i];
			}
	}
	inline int ask(Re L){
		Re ans=0;
		for(Re i=logN;i>=0;--i)if(ip[i]>=L)ans=max(ans,ans^p[i]);
		return ans;
	}
}A[N],S[N];
int main(){
//    freopen("456.txt","r",stdin);
    in(n);
    for(Re i=1;i<=n;++i)in(x),S[i]=S[i-1],S[i].insert(x,i);
    in(T);
    while(T--)in(x),in(y),printf("%d\n",S[y].ask(x));
}
矩阵快速幂 结构体 7.7.5 线性代数与高斯消元
48 行
CPP JSON
【矩阵快速幂(结构体)】 矩阵运算模板(乘法、快速幂、求逆)。 核心函数: void in(Re &x) — 核心算法函数 void read(无参数) — 核心算法函数 void print(无参数) — 核心算法函数 Matrix mi(Matrix x,Re k) — 核心算法函数 核心结构体:Matrix 关键配置: N=103,P=1e9+7
C++ 47 行 CPP
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register LL
const int N=103,P=1e9+7;
LL n,K;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct Matrix{
	LL a[N][N];
	Matrix(){memset(a,0,sizeof(a));}
	inline void read(){
		for(Re i=1;i<=n;++i)
    		for(Re j=1;j<=n;++j)	
    			in(a[i][j]);
	}
	inline void print(){
		for(Re i=1;i<=n;puts(""),++i)
    		for(Re j=1;j<=n;++j)	
    			printf("%lld ",a[i][j]);
	}
	inline Matrix operator*(const Matrix &O)const{
		Matrix ans;
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=n;++j)
				for(Re k=1;k<=n;++k)
					(ans.a[i][j]+=a[i][k]*O.a[k][j]%P)%=P;
		return ans;
	}
	inline Matrix operator*=(Matrix &O){return *this=*this*O;}
}A;
inline Matrix mi(Matrix x,Re k){
	if(!k)return x;--k;
	Matrix s=x;
	while(k){
		if(k&1)s*=x;
		x*=x,k>>=1;
	}
	return s;
}
int main(){
	in(n),in(K),A.read(),mi(A,K).print();
}
28 行
CPP JSON
【线性基】 线性代数模板。 核心函数: void in(Re &x) — 核心算法函数 void insert(Re x) — 插入元素 关键配置: N=55 说明:freopen("123.txt","r",stdin);
C++ 27 行 CPP
#include<algorithm>
#include<cstdio>
#define LL long long
#define Re register LL
using namespace std;
const int N=55;
LL n,x,ans,p[N];
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
inline void insert(Re x){
	for(Re i=50;i>=0;--i)
		if((x>>i)&1){
			if(!p[i]){p[i]=x;break;}
			x^=p[i];
		}
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n);
	for(Re i=1;i<=n;++i)in(x),insert(x);
	for(Re i=50;i>=0;--i)ans=max(ans,ans^p[i]);
	printf("%lld\n",ans);
}
线性基合并 幸运数字 7.7.5 线性代数与高斯消元
62 行
CPP JSON
【线性基合并(幸运数字)】 线性代数模板。 核心函数: void add(Re x,Re y) — 加法更新 void in(Re &x) — 核心算法函数 void insert(Re x) — 插入元素 void merge(JI O) — 合并操作 LL ask(无参数) — 核心算法函数 void dfs(Re x,Re fa) — 深度优先搜索遍历 JI ask(Re x,Re y) — 核心算法函数 核心结构体:QAQ, JI, LCA 说明:freopen("lucky.in","r",stdin);;freopen("lucky.out","w",stdout);
C++ 61 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register LL
using namespace std;
const LL N=2e4+3,M=2e5+3,inf=2e18,logN=14;
LL n,m,o,x,y,T,A[N],head[N];
struct QAQ{LL to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
struct JI{
    LL p[61];JI(){memset(p,0,sizeof(p));}
    inline void insert(Re x){
        for(Re i=60;i>=0;--i)
            if((x>>i)&1){
                if(!p[i]){p[i]=x;break;}
                x^=p[i];
            }
    }
    inline void merge(JI O){
        for(Re i=60;i>=0;--i)if(O.p[i])insert(O.p[i]);
    }
    inline LL ask(){
        Re ans=0;
        for(Re i=60;i>=0;--i)ans=max(ans,ans^p[i]);
        return ans;
    }
};
struct LCA{
    LL deep[N],fa[N][15],ant[N][15];JI dp[N][15];
    inline void dfs(Re x,Re fa){
        deep[x]=deep[ant[x][0]=fa]+1,dp[x][0].insert(A[fa]);
        for(Re j=1;(1<<j)<=deep[x];++j)ant[x][j]=ant[ant[x][j-1]][j-1],dp[x][j]=dp[x][j-1],dp[x][j].merge(dp[ant[x][j-1]][j-1]);
        for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
    }
    inline JI ask(Re x,Re y){
        JI Ans;Ans.insert(A[x]),Ans.insert(A[y]);
        if(deep[x]<deep[y])swap(x,y);
        for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])Ans.merge(dp[x][i]),x=ant[x][i];
        if(x==y)return Ans;
        for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])Ans.merge(dp[x][i]),Ans.merge(dp[y][i]),x=ant[x][i],y=ant[y][i];
        Ans.merge(dp[x][0]);
        return Ans;
    }
}T1;
int main(){
//    freopen("lucky.in","r",stdin);
//    freopen("lucky.out","w",stdout);
    in(n),in(T),m=n-1;
    for(Re i=1;i<=n;++i)in(A[i]);
    while(m--)in(x),in(y),add(x,y),add(y,x);
    T1.dfs(1,0);
    while(T--)in(x),in(y),printf("%lld\n",T1.ask(x,y).ask());
}
高斯消元 高斯约旦消元 7.7.5 线性代数与高斯消元
39 行
CPP JSON
【高斯消元(高斯约旦消元)】 高斯消元法模板,求解线性方程组、矩阵求逆或行列式计算。 核心函数: int dcmp(Re a) — 核心算法函数 LD Abs(LD a) — 核心算法函数 void in(Re &x) — 核心算法函数 关键配置: N=103 说明:freopen("123.txt","r",stdin);
C++ 38 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LD double
#define LL long long
#define Re register int
using namespace std;
const int N=103;
int n;LD eps=1e-8,a[N][N];
inline int dcmp(Re a){return a<-eps?-1:(a>eps?1:0);}
inline LD Abs(LD a){return dcmp(a)*a;}
inline void in(Re &x){
	Re fu=0;x=0;char ch=getchar();
	while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=fu?-x:x;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n);
	for(Re i=1;i<=n;++i)	
		for(Re j=1;j<=n+1;++j)
			scanf("%lf",&a[i][j]);
	for(Re j=1;j<=n;++j){
		Re w=j;
		for(Re i=j+1;i<=n;++i)
			if(dcmp(Abs(a[i][j])-Abs(a[w][j]))>0)w=i;
		for(Re k=1;k<=n+1;++k)swap(a[j][k],a[w][k]);
		if(!dcmp(a[j][j]))return !puts("No Solution");
		for(Re i=1;i<=n;++i)
			if(i!=j){
				LD tmp=a[i][j]/a[j][j];
				for(Re k=j;k<=n+1;++k)a[i][k]-=a[j][k]*tmp;
			}
	}
	for(Re i=1;i<=n;++i)printf("%.2lf\n",a[i][n+1]/a[i][i]);
}
异或线性基 xianxingji 7.7.6 线性基
17 行
CPP JSON
【异或线性基(XOR Basis)】 ▪ Basis() — 构造函数,memset 清零 60 位基数组 a[] ▪ ins(x) — 插入数 x 到线性基:从高位向低位扫描,若 x 第 i 位为 1:若 a[i]==0 则 a[i]=x 返回 true(成功插入);否则 x^=a[i] 继续消去该位。返回 false 表示 x 可被已有基线性表出 ▪ max_val(x=0) — 查询与 x 异或的最大值:贪心从高到低,若 (x^a[i])>x 则 x^=a[i] 基的大小 ≤60(long long 位数)。适用于最大异或和、判断数是否可被表出、线性基求第 k 小异或和等。
C++ 17 行 CPP
struct Basis{
    static const int K=60;
    ll a[K];
    Basis(){memset(a,0,sizeof a);}
    bool ins(ll x){
        for(int i=K-1;~i;--i)
        if(x>>i&1){
            if(!a[i]){a[i]=x;return true;}
            x^=a[i];
        }
        return false;
    }
    ll max_val(ll x=0){
        for(int i=K-1;~i;--i)if((x^a[i])>x)x^=a[i];
        return x;
    }
}B;
前缀基 b 7.7.6 线性基
38 行
CPP JSON
【前缀基(b)】 前缀线性基模板,维护每个位置的前缀线性基并可查询区间异或最大值。 核心函数: ll qpow(ll a, ll b) — 快速幂 void linear_inv(const std::vector<ll>& a, std::vector<ll>& inv_a) — 求模逆元 关键配置: MOD=998244353
C++ 38 行 CPP
#include <iostream>
#include <vector>

using ll = long long;
using namespace std;
const int MOD = 998244353;

ll qpow(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

/**
 * 线性批量求逆元 (前缀积法)
 * 传入需要求逆元的数组 a (1-indexed),将结果存入 inv_a (1-indexed)
 * 时间复杂度: O(n + log(MOD))
 */
void linear_inv(const std::vector<ll>& a, std::vector<ll>& inv_a) {
    int n = a.size() - 1;
    if (n <= 0) return;
    std::vector<ll> pre(n + 1, 1), inv_pre(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] * a[i] % MOD;
    }
    inv_pre[n] = qpow(pre[n], MOD - 2);
    for (int i = n; i >= 1; i--) {
        inv_pre[i - 1] = inv_pre[i] * a[i] % MOD;
    }
    for (int i = 1; i <= n; i++) {
        inv_a[i] = inv_pre[i] * pre[i - 1] % MOD;
    }
}
已复制