各种模板（数学&数论&字符串）

各种模板（数学&数论&字符串）

文章目录

• 数学&数论
• • 线性求逆元
  • exgcd
  • excrt
  • FFT
  • NTT
  • 矩阵乘法
  • 线性筛素数
  • 杜教筛
• 字符串
• • Trie
  • KMP
  • hash
  • Manacher
  • AC自动机
  • PAM
  • SAM
  • 广义SAM

数学&数论 线性求逆元

#include
#include
#include
#include
#define ll long long
#define N 3001000
using namespace std;
ll n,p,q[N];
int main()
{
	scanf("%lld%lld",&n,&p);
	q[1]=1;
	for(ll i=2;i<=n;++i)
		q[i]=p-p/i*q[p%i]%p;
	return 0;
}

exgcd

#include
#include
#include
#include
#define ll long long
using namespace std;
int n,p,x,y;
void exgcd(int a,int b,int &x,int &y)
{
	if(!b){
		x=1;y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	int z=x;
	x=y;y=z-a/b*y;
	return;
}
int get(int a,int p)
{
	exgcd(a,p,x,y);
	return (x+p)%p;
}
int main()
{
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;++i)
		printf("%dn",get(i,p));
	return 0;
}

excrt

#include
#include
#include
#include
#define ll long long
#define N 100100
using namespace std;
ll n,X,M,a[N],m[N];
ll ksc(ll x,ll y,ll wyc)
{
	return (x*y-(ll)((long double)x*y/wyc)*wyc+wyc)%wyc;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b){
		x=1;y=0;
		return a;
	}
	ll d=exgcd(b,a%b,x,y),z=x;
	x=y;y=z-a/b*y;
	return d;
}
void excrt()
{
	ll x,y;
	X=a[1],M=m[1];
	for(ll i=2;i<=n;++i){
		ll A=M,B=m[i],c=(a[i]-X%B+B)%B;
		ll d=exgcd(A,B,x,y);
		if(c%d){
			X=-1;
			return;
		}
		x=ksc(x,c/d,B/d);
		X+=x*M;
		M*=B/d;
		X=(X%M+M)%M;
	}
	return;
}
int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i)
		scanf("%lld%lld",&m[i],&a[i]);
	excrt();
	printf("%lld",X);
	return 0;
}

FFT

#include
#include
#include
#include
#include
#define ll long long
#define N 1000010
using namespace std;
const double Pi=acos(-1);
int n,m,r[N<<2];
struct CP
{
	CP(double xx=0,double yy=0){x=xx,y=yy;}
	double x,y;
	CP operator +(CP const &b)const
	{return CP(x+b.x,y+b.y);}
	CP operator -(CP const &b)const
	{return CP(x-b.x,y-b.y);}
	CP operator *(CP const &b)const
	{return CP(x*b.x-y*b.y,x*b.y+y*b.x);}
}f[N<<2],g[N<<2];
void fft(CP *f,int flag)
{
	for(int i=0;i>1;
		CP G(cos(2*Pi/p),sin(2*Pi/p)*flag);
		for(int k=0;k>1]>>1)|(i&1?n>>1:0);
	fft(f,1);
	fft(g,1);
	for(int i=0;i 
NTT 
#include
#include
#include
#include
#define ll long long
#define N 1000100
#define mod 998244353
using namespace std;
ll n,m,G,invn,invG,f[N<<2],g[N<<2],tr[N<<2];
ll Counting(ll x,ll y)
{
	ll z=1;
	while(y){
		if(y&1)z=z*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return z;
}
void ntt(ll *f,ll flag)
{
	for(ll i=0;i>1,tG=Counting((flag?G:invG),(mod-1)/p);
		for(ll k=0;k>1]>>1)|(i&1?n>>1:0);
	ntt(f,1);ntt(g,1);
	for(ll i=0;i 
矩阵乘法 
#include
#include
#include
#include
#define ll long long
#define wyc 1000000007
ll n;
struct matrix
{
	ll n, m, a[5][5];
	matrix operator *(const matrix b) const
	{
		matrix c;
		c.n = n;
		c.m = b.m;
		for (ll i = 1; i <= c.n; ++i)
			for (ll j = 1; j <= c.m; ++j)
				c.a[i][j] = 0;
		for (ll i = 1; i <= n; ++i)
			for (ll k = 1; k <= m; ++k)
				for (ll j = 1; j <= b.m; ++j)
					c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % wyc) % wyc;
		return c;
	}
}A, B;
void ksm(ll g)//快速幂
{
	while(g)
	{
		if (g & 1) A = A * B;
		B = B * B;
		g>>=1;
	}
}
int main()
{
	scanf("%lld", &n);
	B.n = 2;
	B.m = 2;
	B.a[1][1] = 0;
	B.a[1][2] = 1;
	B.a[2][1] = 1;
	B.a[2][2] = 1;
	A.n = 1;
	A.m = 2;
	A.a[1][1] = 1;
	A.a[1][2] = 1;
	ksm(n - 1);
	printf("%lld", A.a[1][1]);
	return 0;
}
 
线性筛素数 
#include
#include
#include
#include
#define ll long long
using namespace std;
int n, q, x, w, prime[6000000];
bool p[100000010];
void work(int n)
{
	for (int i = 2; i <= n; ++i)
	{
		if (!p[i]) prime[++w] = i;
		for (int j = 1; j <= w && i * prime[j] <= n; ++j)
		{
			p[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
		}
	}
	return;
}
int main()
{
	scanf("%d%d", &n, &q);
	work(n);
	for (int i = 1; i <= q; ++i)
	{
		scanf("%d", &x);
		printf("%dn", prime[x]);
	}
	return 0;
}
 
杜教筛 
#include
#include
#include
#include
#define ll long long
#define MXN 5000100
using namespace std;
ll T,N,w,smu[2010],sphi[2010],mu[MXN],phi[MXN],prime[MXN],p[MXN];
const ll MX=5000000;
void work()
{
	mu[1]=phi[1]=1;
	for(ll i=2;i<=MX;++i){
		if(!p[i]){
			prime[++w]=i;
			phi[i]=i-1;
			mu[i]=-1;
		}
		for(ll j=1;j<=w&&i*prime[j]<=MX;++j){
			p[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else{
				mu[i*prime[j]]=-mu[i];
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
		}
	}
	for(ll i=2;i<=MX;++i)
		mu[i]+=mu[i-1],phi[i]+=phi[i-1];
	return;
}
ll get_mu(ll n)
{
	if(n<=MX)return mu[n];
	else return smu[N/n];
}
ll get_phi(ll n)
{
	if(n<=MX)return phi[n];
	else return sphi[N/n];
}
void S(ll n,ll d)
{
	if(n<=MX||sphi[d])return;
	smu[d]=1;
	sphi[d]=n*(n+1)/2;
	for(ll l=2,r=0;l<=n;l=r+1){
		r=n/(n/l);
		S(n/l,d*l);
		smu[d]-=get_mu(n/l)*(r-l+1);
		sphi[d]-=get_phi(n/l)*(r-l+1);
	}
	return;
}
int main()
{
	work();
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&N);
		memset(sphi,0,sizeof(sphi));
		S(N,1);
		printf("%lld %lldn",get_phi(N),get_mu(N));
	}
	return 0;
}
 
字符串 
Trie 
#include
#include
#include
#include
#define ll long long
#define N 1000100
using namespace std;
int n, m, w, a[N], to[N][30];
char s[N];
void insert(char* s)
{
	int n = strlen(s+1), x = 0, y;
	for (int i = 1; i <= n; ++i)
	{
		y = s[i] - 'a';
		if (!to[x][y]) to[x][y] = ++w;
		x = to[x][y];
	}
	a[x]++;
	return;
}
int ask(char* s)
{
	int n = strlen(s+1), x = 0, y, ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		y = s[i] - 'a';
		if (to[x][y]) x = to[x][y];
		else return ans;
		ans += a[x];
	}
	return ans;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", s+1);
		insert(s);
	}
	while(m--)
	{
		scanf("%s", s+1);
		printf("%dn", ask(s));
	}
	return 0;
}
 
KMP 
#include 
#include 
#include 
#include 
#define ll long long
#define N 1000100
using namespace std;
int nx[N];
char s[N], str[N];
void gnx(char* s) {
    int n = strlen(s + 1);
    for (int i = 2, j = 0; i <= n; ++i) {
        while (s[i] != s[j + 1] && j) j = nx[j];
        if (s[i] == s[j + 1])
            j++;
        nx[i] = j;
    }
    return;
}
int match(char* s, char* str) {
    int n = strlen(s + 1), m = strlen(str + 1), ans = 0;
    for (int i = 1, j = 0; i <= m; ++i) {
        while ((j == n || str[i] != s[j + 1]) && j) j = nx[j];
        if (str[i] == s[j + 1])
            j++;
        if (j == n)
            ans++;
    }
    return ans;
}
int main() {
    scanf("%s%s", str + 1, s + 1);
    gnx(s);
    printf("%d", match(s, str));
    return 0;
}
 
hash 
#include
 
Manacher 
#include
#include
#include
#include
#define ll long long
#define N 110000010
using namespace std;
int n, ans, l[N*2], s[N*2];
string str;
void Manacher()
{
	int mid = 0, mx = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (i < mx) l[i] = min(l[mid * 2 - i], mx - i);
		else l[i] = 1;
		while(s[i + l[i]] == s[i - l[i]]) l[i]++;
		if (i + l[i] > mx)
		{
			mid = i;
			mx = i + l[i];
		}
		ans = max(ans, l[i]);
	}
	return;
}
int main()
{
	cin>>str;
	n = str.size();
	s[0] = s[1] = '#';
	for (int i = 1; i <= n; ++i)
	{
		s[i * 2] = str[i - 1];
		s[i * 2 + 1] = '#';
	}
	n = n * 2 + 2;
	s[n] = 0;
	Manacher();
	printf("%d", ans - 1);
	return 0;
}
 
AC自动机 
#include
#include
#include
#include
#include
#define ll long long
#define N 20100
using namespace std;
int n, w, ans, a[200], v[N], nx[N], to[N][30];
char s[200][100], ss[1000100];
queued;
void insert(char* s, int g)
{
	int n = strlen(s+1), now = 0, y;
	for (int i = 1; i <= n; ++i)
	{
		y = s[i] - 'a';
		if (!to[now][y]) to[now][y] = ++w;
		now = to[now][y];
	}
	v[now] = g;
	return;
}
void bfs()
{
	for (int i = 0; i < 26; ++i)
		if (to[0][i]) d.push(to[0][i]);
	while(!d.empty())
	{
		int h = d.front();
		d.pop();
		for (int i = 0; i < 26; ++i)
			if (!to[h][i]) to[h][i] = to[nx[h]][i];
			else nx[to[h][i]] = to[nx[h]][i], d.push(to[h][i]);
	}
	return;
}
void ask(char* s)
{
	int n = strlen(s+1), now = 0, y, g;
	for (int i = 1; i <= n; ++i)
	{
		y = s[i] - 'a';
		now = g = to[now][y];
		while(g)
		{
			if (v[g]) a[v[g]]++;
			g = nx[g];
		}
	}
	return;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", s[i]+1);
		insert(s[i], i);
	}
	bfs();
	scanf("%s", ss+1);
	ask(ss);
	for (int i = 1; i <= n; ++i)
		ans = max(ans, a[i]);
	printf("%dn", ans);
	for (int i = 1; i <= n; ++i)
		if (a[i] == ans)
			printf("%sn", s[i]+1);
	return 0;
}

 
PAM 
#include
#include
#include
#include
#define ll long long
#define N 500010
using namespace std;
int n,k,last;
char s[N];
struct PAM
{
	int nm,now,c[N],len[N],num[N],fail[N],to[N][30];
	void pre_work()
	{
		now=1;
		len[1]=-1;
		fail[0]=1;
		c[0]=-1;
		last=0;
		return;
	}
	int get_fail(int x)
	{
		while(c[nm]!=c[nm-len[x]-1])x=fail[x];
		return x;
	}
	void add(int x)
	{
		c[++nm]=x;
		int ls=get_fail(last);
		if(!to[ls][x]){
			len[++now]=len[ls]+2;
			fail[now]=to[get_fail(fail[ls])][x];
			to[ls][x]=now;
			num[now]=num[fail[now]]+1;
		}
		last=to[ls][x];
	}
}T;
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	T.pre_work();
	for(int i=1;i<=n;++i){
		s[i]=(s[i]-97+k)%26;
		T.add(s[i]);
		k=T.num[last];
		printf("%d ",k);
	}
	return 0;
}

 
SAM 
#include
#include
#include
#include
#define ll long long
#define N 1000100
using namespace std;
ll n,w,tot,lst,ans,h[N<<1],fa[N<<1],ch[N<<1][26],len[N<<1],num[N<<1];
char s[N];
struct rec
{
	ll to,nx;
}e[N<<1];
void add(ll c)
{
	ll p=lst,np=lst=++w;
	len[np]=len[p]+1;
	num[np]=1;
	while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
	if(!p)fa[np]=1;
	else{
		ll q=ch[p][c];
		if(len[q]==len[p]+1)fa[np]=q;
		else{
			ll nq=++w;
			len[nq]=len[p]+1;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			while(p&&ch[p][c]==q)ch[p][c]=nq,p=fa[p];
		}
	}
	return;
}
void addl(ll x,ll y)
{
	e[++tot].to=y;
	e[tot].nx=h[x];
	h[x]=tot;
	return;
}
void dfs(ll x)
{
	for(ll i=h[x];i;i=e[i].nx){
		ll y=e[i].to;
		dfs(y);
		num[x]+=num[y];
	}
	if(num[x]>1)ans=max(ans,num[x]*len[x]);
	return;
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	lst=w=1;
	for(ll i=1;i<=n;++i)
		add(s[i]-'a');
	for(ll i=2;i<=w;++i)
		addl(fa[i],i);
	dfs(1);
	printf("%lld",ans);
	return 0;
}

 
广义SAM 
#include
#include
#include
#include
#define ll long long
#define N 1000100
using namespace std;
ll n,m,w,lst,ans,fa[N<<1],len[N<<1],ch[N<<1][30];
char s[N];
ll add(ll x,ll c)
{
	ll p=x;
	if(ch[p][c]){
		ll q=ch[p][c];
		if(len[q]==len[p]+1)return q;
		else{
			ll nq=++w;
			len[nq]=len[p]+1;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[nq]=fa[q];
			fa[q]=nq;
			while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];
			return nq;
		}
	}
	ll np=++w;
	len[np]=len[p]+1;
	while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
	if(!p)fa[np]=1;
	else{
		ll q=ch[p][c];
		if(len[q]==len[p]+1)fa[np]=q;
		else{
			ll nq=++w;
			len[nq]=len[p]+1;
			memcpy(ch[nq],ch[q],sizeof(ch[q]));
			fa[nq]=fa[q];
			fa[q]=fa[np]=nq;
			while(p&&ch[p][c]==q)ch[p][c]=nq,p=fa[p];
		}
	}
	return np;
}
int main()
{
	scanf("%lld",&n);
	w=1;
	for(ll i=1;i<=n;++i){
		scanf("%s",s+1);
		m=strlen(s+1);
		lst=1;
		for(ll i=1;i<=m;++i)
			lst=add(lst,s[i]-'a');
	}
	for(ll i=2;i<=w;++i)
		ans+=len[i]-len[fa[i]];
	printf("%lld",ans);
	return 0;
}

					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5651840.html