文章目錄

• 數(shù)學(xué)&數(shù)論
• • 線性求逆元
  • exgcd
  • excrt
  • FFT
  • NTT
  • 矩陣乘法
  • 線性篩素?cái)?shù)
  • 杜教篩
• 字符串
• • Trie
  • KMP
  • hash
  • Manacher
  • AC自動(dòng)機(jī)
  • PAM
  • SAM
  • 廣義SAM

數(shù)學(xué)&數(shù)論

線性求逆元

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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("%d\n",get(i,p));return 0; }

excrt

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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<n;++i)if(i<r[i])swap(f[i],f[r[i]]);for(int p=2;p<=n;p<<=1){int len=p>>1;CP G(cos(2*Pi/p),sin(2*Pi/p)*flag);for(int k=0;k<n;k+=p){CP buf(1,0);for(int i=k;i<k+len;++i){CP g=buf*f[i+len];f[i+len]=f[i]-g;f[i]=f[i]+g;buf=buf*G;}}}return; } int main() {scanf("%d%d",&n,&m);n++,m++;for(int i=0;i<n;++i)scanf("%lf",&f[i].x);for(int i=0;i<m;++i)scanf("%lf",&g[i].x);for(m+=n,n=1;n<m;n<<=1);for(int i=0;i<n;++i)r[i]=(r[i>>1]>>1)|(i&1?n>>1:0);fft(f,1);fft(g,1);for(int i=0;i<n;++i)f[i]=f[i]*g[i];fft(f,-1);for(int i=0;i<=m-2;++i)printf("%d ",(int)(f[i].x/n+0.5));return 0; }

NTT

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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<n;++i)if(i<tr[i])swap(f[i],f[tr[i]]);for(ll p=2;p<=n;p<<=1){ll len=p>>1,tG=Counting((flag?G:invG),(mod-1)/p);for(ll k=0;k<n;k+=p){ll buf=1;for(ll i=k;i<k+len;++i){ll tt=buf*f[i+len]%mod;f[i+len]=(f[i]-tt+mod)%mod;f[i]=(f[i]+tt)%mod;buf=buf*tG%mod;}}}return; } int main() {scanf("%lld%lld",&n,&m);n++,m++;for(ll i=0;i<n;++i)scanf("%lld",&f[i]);for(ll i=0;i<m;++i)scanf("%lld",&g[i]);for(m+=n,n=1;n<m;n<<=1);G=3;invG=Counting(3,mod-2);invn=Counting(n,mod-2);for(ll i=0;i<n;++i)tr[i]=(tr[i>>1]>>1)|(i&1?n>>1:0);ntt(f,1);ntt(g,1);for(ll i=0;i<n;++i)f[i]=f[i]*g[i]%mod;ntt(f,0);for(ll i=0;i<=m-2;++i)printf("%lld ",f[i]*invn%mod);return 0; }

矩陣乘法

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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; }

線性篩素?cái)?shù)

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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("%d\n", prime[x]);}return 0; }

杜教篩

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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 %lld\n",get_phi(N),get_mu(N));}return 0; }

字符串

Trie

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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("%d\n", ask(s));}return 0; }

KMP

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #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<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define ull unsigned long long using namespace std; int n, l, ans; ull x[10010]; char s[1510]; int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i){scanf("%s", s+1);l = strlen(s+1);for (int j = 1; j <= l; ++j)x[i] = x[i] * 131llu + s[j];}sort(x + 1, x + 1 + n);for (int i = 1; i <= n; ++i)if (x[i] != x[i - 1] || i == 1) ans++;printf("%d", ans);return 0; }

Manacher

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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自動(dòng)機(jī)

#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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]; queue<int>d; 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("%d\n", ans);for (int i = 1; i <= n; ++i)if (a[i] == ans)printf("%s\n", s[i]+1);return 0; }

PAM

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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; }

總結(jié)

以上是生活随笔為你收集整理的各种模板（数学数论字符串）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。