一、基本： 当我们遍历到 某个 节点的时候,由于存在这个节点,我们就让他的fail指针 指向 他父亲节点的fail指针指向的那个节点的具有相同字母的子节点。 简单来说，AC自动机是用来进行多模式匹配（单个主串，多个模式串）的高效算法。 使用Aho-Corasick算法需要三步： 建立模式串的Trie 给Trie添加失败路径 根据AC自动机，搜索待处理的文本 例题：Keywords Search HDU - 2222 In the modern time, Search engine came into the life of everybody like Google, Baidu, etc....

一、不挣扎了，直接背。         首先，回文树有何功能？ 假设我们有一个串S，S下标从0开始，则回文树能做到如下几点： 1.求串S前缀0~i内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同） 2.求串S内每一个本质不同回文串出现的次数 3.求串S内回文串的个数（其实就是1和2结合起来） 4.求以下标i结尾的回文串的个数             这里有个很巧妙的地方，0作为偶数串的根，1作为奇数串的根。 板子： 设字符集大小为m，母串长度为n，则空间复杂度为O(nm)，时间复杂度为O(nlogm) p：不同回文串的种类，本质不同串的个数； last：指向 ...

一、 贴代码： #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cstdlib> #include<ctime> #define ll long long using namespace std; const int s=8;//随机算法判定次数，8--10左右 //记得把龟速乘换成快速乘 ll mult_mod(ll a,ll b,ll c) { a%=c; ...

一、不取模直接运算。 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #define ll long long using namespace std; const int maxn=62; ll c[maxn][maxn]; ll _c[maxn][maxn]; ll C(ll n, ll m) { ll res=1; for(ll i=1;i<=m;i++) { res=res*(n-m+i)...

一、线性筛  const int maxn=1000006; int prime[maxn]; bool ha[maxn]; int mu[maxn]; int cnt=0; void Mu(void) { mu[1]=1; ha[1]=true; for(int i=2;i<maxn;i++) { if(!ha[i]) { mu[i]=-1; prime[cnt++]=i; } for(int j=0;j<cnt&&(ll)i*prime[j]<maxn;j++) { ha[i*prime[j]]=true; if(i%prime[j]==0) { mu[i...

一、标版： 题目描述 现有两组数字，每组k个，第一组中的数字分别为：a1，a2，…，ak表示，第二组中的数字分别用b1，b2，…，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n - ai能被bi整除。 输入输出格式 输入格式： 输入数据的第一行是一个整数k，（1 ≤ k ≤ 10）。接下来有两行，第一行是：a1，a2，…，ak，第二行是b1，b2，…，bk 输出格式： 输出所求的整数n。 输入输出样例 输入样例#1： 3 1 2 3 2 3 5 输出样例#1： 23 说明 所有数据中，第一组数字的绝对值不超过109（可能为负数），第二组数字均为不超过6000...

一、算法进阶给的板子： int bsgs(int a,int b,int p) { map<int,int>_hash; _hash.clear(); b%=p; int t=(int) sqrt(p)+1; for(int j=0;j<t;j++) { int val=(ll) b*power(a,j,p)%p; _hash[val]=j; } a=power(a,t,p); if(a==0) return b==0?1:-1; for(int i=0;i<=t;i++) { int val=power(a,i,p); int j=_hash.find(val)==_...

一、多重集的组合数： #include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<cmath> #include<string> #define ll long long using namespace std; const int p=1000000007; const int maxn=25; ll a[maxn],inv[maxn]; ll n,m,ans=0; ll mypow(ll a,ll b) { ll ...

一、整数高斯消元： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> #include<cmath> #define ll long long using namespace std; const int maxn=20; int gcd(int a,int b) { if(b==0) return a; else return gcd(b,a%b); } int lcm(int a,int ...

一、建树、单点修改、单点查询、区间修改、区间查询： 单点修改、区间查询： #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn = 500010; struct node { int sum; int l,r; }tree[maxn*4]; int a[maxn]; void bulid(int l,int r,int cnt) { tre...

POJ2689 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<string> #include<cmath> #define ll long long using namespace std; const int maxn=1000006; bool ha[maxn]={false}; int prime[maxn]; int cnt=0; void Pri...

POJ1811 #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<string> #include<ctime> #include<cmath> #define ll long long using namespace std; const int s=8; //记得把龟速乘换成快速乘 ll mult_mod(ll a,ll b,ll c) { a%...

1。 这其实是龟速乘 ll mul(ll a,ll b) { ll ans=0; while(b) { if(b&1) ans=(ans+a)%mod; a=(a+a)%mod; b>>=1; } return ans; }  2。 这个是O（1） 乘 ll mul(ll a,ll b,ll p) { a%=p,b%=p; ll c=(long double)a*b/p; ll ans=a*b-c*p; if(ans<0) ans+=p; else if(ans>=p) ans-=p; return ans; }

P4345 [SHOI2015]超能粒子炮·改 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<vector> #define ll long long using namespace std; const int mod=2333; const int maxn=mod+2; int sum[maxn][maxn]; int c...