$\color{red} {基础算法}$
$\color{green} {manacher算法}$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e7+1e2;
char a[N],b[N];
ll p[N];
ll n,k;
void init()
{
b[k++]='$',b[k++]='#';
for(ll i=0;i<n;i++)b[k++]=a[i],b[k++]='#';
b[k++]='^';
}
void manacher()
{
ll mr=0,mid;
for(ll i=1;i<k;i++)
{
if(i<mr)p[i]=min(p[mid*2-i],mr-i);
else p[i]=1;
while(b[i-p[i]]==b[i+p[i]])p[i]++;
if(i+p[i]>mr)
{
mr=i+p[i];
mid=i;
}
}
}
ll ans;
signed main()
{
scanf("%s",a);
n=strlen(a);
init();
manacher();
for(ll i=0;i<k;i++)ans=max(ans,p[i]);
cout<<ans-1;
}
$\color{red} {搜索}$
$\color{green} {模拟退火}$
$\color{green} {爬山法}$
$\color{green} {牛顿迭代法}$
决策点 $x_{n+1}=x_n- \frac{f(x_n)}{f^{‘}(x_{n})}$
$\color{red} {数学}$
$\color{green} {线性递推逆元表}$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e7+1e3;
ll n,mod,ny[N];
signed main()
{
cin>>n>>mod;
ny[1]=1;
for(ll i=2;i<=n;i++)
ny[i]=(mod-mod/i)*ny[mod%i]%mod;
}
$\color{green} {莫比乌斯反演}$
$\color{purple} {莫比乌斯函数}$
对于 $x=P_1^{\alpha_1} P_2^{\alpha_2} ......P_k^{\alpha_k} $，其中$P_i$为质数，$\alpha_i \ge 1$
定义 $\mu(x)$如下：
$$\mu(x)\bigg\{^{0\ \ \ \ \alpha_i\ge2}_{(-1)^k\ \ \ \ \forall \alpha_i=1}$$
记 $S(n)=\sum_{d \mid n}^{n} \mu(d)$,那么：
$$S(n)= \bigg\{^{1\ \ \ \ n=1}_{(-1)^k\ \ \ \ n\ge2}$$
$\color{purple} {莫比乌斯反演定理1}$
若$F(n)=\sum_{d \mid n}f(n)$，则：
$$f(n)=\sum_ {d\mid n} \mu(d)F(\frac{n}{d})$$
$\color{purple} {莫比乌斯反演定理2}$
若$F(n)=\sum_{n \mid d}f(d)$，则：
$$f(n)=\sum_ {n\mid d} \mu(\frac{d}{n})F(d)$$
$\color{green} {积性函数}$
$\color{green} {卢卡斯定理/Lucas 定理}$
解决问题：
求出 $C_{n+m}^{m}$ $mod$ $p$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e4;
ll n,m,p;
ll a[N];
ll quick_mi(ll a,ll b)
{
ll s=1;
while(b)
{
if(b&1)s=s*a%p;
a=a*a%p;
b>>=1;
}
return s;
}
ll C(ll n,ll m)
{
if(m>n)return 0;
return (((a[n]*quick_mi(a[m],p-2))%p)*(quick_mi(a[n-m],p-2)))%p;
}
ll Lucas(ll n,ll m)
{
if(!m)return 1;
return (C(n%p,m%p)*Lucas(n/p,m/p))%p;
}
ll ans;
ll t;
signed main()
{
cin>>t;
while(t--)
{
cin>>n>>m>>p;
a[0]=1;
for(ll i=1;i<=p;i++)a[i]=(a[i-1]*i)%p;
cout<<Lucas(n+m,m)<<"\n";
}
}
$\color{green} {扩展欧拉定理}$
解决问题：
求出 $a^b\ mod\ p$。
其中 $b$ 非常大，如题 $b \le 10^{20000000}$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,m;
ll quick_mi(ll a,ll b)
{
ll s=1;
while(b)
{
if(b&1)s=s*a%m;
a=a*a%m;
b>>=1;
}
return s;
}
signed main()
{
cin>>a>>m;
ll cm=m;
double fm1=m;
for(ll i=2;i*i<=cm;i++)
{
if(cm%i)continue;
while(cm%i==0)cm/=i;
fm1*=(1.0-(double)1.0/i);
}
if(cm!=1)fm1*=(1.0-(double)1.0/cm);
ll fm=fm1;
char c;
while((c=getchar())<'0'||c>'9');
ll k=0;
bool flag=false;
while(k=(k<<1)+(k<<3)+(c^48),(c=getchar())>='0'&&c<='9')
if(k>=fm)flag=true,k%=fm;
if(k>=fm)flag=true,k%=fm;
if(flag)k+=fm;
cout<<quick_mi(a,k);
}
$\color{green} {拓展欧几里得}$
ll exgcd(ll a,ll b,ll& x,ll& y)
{
if(!b)
{
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
$\color{green} {BSGS}$
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
ll a,p,b;
ll bsgs(ll a,ll p,ll b)
{
if(1%p==b%p)return 0;
ll k=sqrt(p)+1;
unordered_map<ll,ll>hash;
for(ll i=0,j=b%p;i<k;i++)
{
hash[j]=i;
j*=a,j%=p;
}
ll ak=1;
for(ll i=1;i<=k;i++)ak*=a,ak%=p;
for(ll i=1,j=ak;i<=k;i++)
{
if(hash.count(j))return i*k-hash[j];
j*=ak,j%=p;
}
return -1;
}
signed main()
{
while(cin>>a>>p>>b,a||b||p)
{
ll res=bsgs(a,p,b);
if(res==-1)puts("No Solution");
else cout<<res<<"\n";
}
}
$\color{green} {扩展BSGS}$
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
typedef long long ll;
const ll INF=1e12;
ll a,p,b;
ll exgcd(ll a,ll b,ll& x,ll& y)
{
if(!b)
{
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll bsgs(ll a,ll b,ll p)
{
if(1%p==b%p)return 0;
ll k=sqrt(p)+1;
unordered_map<ll,ll>hash;
for(ll i=0,j=b%p;i<k;i++)
{
hash[j]=i;
j*=a,j%=p;
}
ll ak=1;
for(ll i=1;i<=k;i++)ak*=a,ak%=p;
for(ll i=1,j=ak;i<=k;i++)
{
if(hash.count(j))return i*k-hash[j];
j*=ak,j%=p;
}
return -INF;
}
ll exbsgs(ll a,ll b,ll p)
{
b=(b%p+p)%p;
if(1%p==b%p)return 0;
ll x,y;
ll d=exgcd(a,p,x,y);
if(d>1)
{
if(b%d)return -INF;
exgcd(a/d,p/d,x,y);
return exbsgs(a,b/d*x%(p/d),p/d)+1;
}
return bsgs(a,b,p);
}
signed main()
{
while(cin>>a>>p>>b,a||p||b)
{
ll res=exbsgs(a,b,p);
if(res<0)puts("No Solution");
else cout<<res<<"\n";
}
}
$\color{green} {FFT}$
//多项式乘法
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5*3+1e4;
const double PI=acos(-1);
ll n,m;
struct Complex
{
double x,y;
Complex operator+ (const Complex& P)const
{
return {x+P.x,y+P.y};
}
Complex operator- (const Complex& P)const
{
return {x-P.x,y-P.y};
}
Complex operator* (const Complex& P)const
{
return {x*P.x-y*P.y,x*P.y+y*P.x};
}
}a[N],b[N];
ll rev[N],bit,tot;
void fft(Complex a[],ll inv)
{
for(ll i=0;i<tot;i++)
if(i<rev[i])
swap(a[i],a[rev[i]]);
for(ll mid=1;mid<tot;mid<<=1)
{
auto w1=Complex({cos(PI/mid),inv*sin(PI/mid)});
for(ll i=0;i<tot;i+=mid*2)
{
auto wk=Complex({1,0});
for(ll j=0;j<mid;j++,wk=wk*w1)
{
auto x=a[i+j],y=wk*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
}
}
signed main()
{
cin>>n>>m;
for(ll i=0;i<=n;i++)cin>>a[i].x;
for(ll i=0;i<=m;i++)cin>>b[i].x;
while((1<<bit)<n+m+1)bit++;
tot=1<<bit;
for(ll i=0;i<tot;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
fft(a,1),fft(b,1);
for(ll i=0;i<tot;i++)a[i]=a[i]*b[i];
fft(a,-1);
for(ll i=0;i<=n+m;i++)
cout<<(ll)(a[i].x/tot+0.5)<<" ";
}
$\color{red} {计算几何}$
$\color{green} {Andrew算法}$
①将点排序：$x$作为第一关键字，$y$作为第二关键字
②从左到右维护上半部分，从右到左维护下半部分
$\color{green} {自适应辛普森积分}$
$\color{purple} {Simpson公式}$
$$
\int_{b}^{a}f(x)dx
\approx\int_a^bAx^2+Bx+C
$$
$$
≈
\int _b^aAx^2+Bx+C
$$
$$
=\frac{A}{3}(b^3-a^3)+\frac{B}{2}(b^2-a^2)+C(a-b)
$$
$$
=\frac{(b-a)}{6}(2A(b^2+ab+a^2)+3B(b+a)+6C)
$$
$$
=\frac{(b-a)}{6}(2Ab^2+2Aab+2Aa^2+3Bb+3Ba+6C)
$$
$$
=\frac{(b-a)}{6}(Aa^2+Ba+C+Ab^2+Bb+C+4A(\frac{a+b}{2})^2+4B(\frac{a+b}{2})+4C)
$$
$$
=\frac{(b-a)}{6}(f(a)+f(b)+4f(\frac{a+b}{2}))
$$
然后就得到了Simpson公式：
$$
\int_a^bf(x)dx\approx\frac{(b-a)(f(a)+f(b)+4f(\frac{a+b}{2}))}{6}
$$
$\color{purple} {自适应辛普森法1}$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e4,M=1e3+1e2;
double f(double x)
{
return sin(x)/x;
}
double simpson(double l,double r)
{
double mid=(r+l)/2.0;
return (r-l)*(f(l)+f(r)+4.0*f(mid))/6.0;
}
double asr(double l,double r,double eps,double ans)
{
double mid=(l+r)/2.0;
double l_=simpson(l,mid),r_=simpson(mid,r);
if(fabs(l_+r_-ans)<=15*eps)return l_+r_+(l_+r_-ans);
return asr(l,mid,eps/2.0,l_)+asr(mid,r,eps/2.0,r_);
}
double a,b;
signed main()
{
cin>>a>>b;
printf("%.6lf",asr(a,b,1e-10,simpson(a,b)));
}
$\color{red} {数据结构}$
$\color{green} {ST表}$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5*2+1e4,M=1e3+1e2;
ll n,m;
ll a[N];
ll l,r;
ll lg2[N];
ll stable[N][30];
void init()
{
for(ll i=1;i<=n;i++)
stable[i][0]=a[i];
for(ll i=1;i<=lg2[n]+1;i++)
{
for(ll j=1;j+(1<<i)-1<=n;j++)
{
stable[j][i]=max(stable[j][i-1],stable[j+(1<<(i-1))][i-1]);
}
}
}
ll ask(ll l,ll r)
{
ll lon=lg2[r-l+1];
return max(stable[l][lon],stable[r-(1<<lon)+1][lon]);
}
signed main()
{
for(ll i=2;i<=N;i++)lg2[i]=lg2[i>>1]+1;
cin>>n;
for(ll i=1;i<=n;i++)cin>>a[i];
init();
cin>>m;
while(m--)
{
cin>>l>>r;
cout<<ask(l,r)<<"\n";
}
}
$\color{green} {线段树}$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e4,M=1e3+1e2;
ll n,m;
ll a[N];
ll l,r,d;
char opt;
struct node
{
ll l,r;
ll sum;
ll add;
}tree[N*4];
void pushup(ll u)
{
tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;
}
void pushdown(ll u)
{
if(tree[u].add==0)return ;
auto &left=tree[u<<1],&right=tree[u<<1|1];
left.add+=tree[u].add,left.sum+=(left.r-left.l+1)*tree[u].add;
right.add+=tree[u].add,right.sum+=(right.r-right.l+1)*tree[u].add;
tree[u].add=0;
}
void build(ll u,ll l,ll r)
{
if(l==r)
{
tree[u].l=tree[u].r=l;
tree[u].sum=a[l];
return ;
}
else
{
tree[u].l=l,tree[u].r=r;
ll mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void change(ll u,ll l,ll r)
{
if(tree[u].l>=l&&tree[u].r<=r)
{
tree[u].add+=d;
tree[u].sum+=(tree[u].r-tree[u].l+1)*d;
return ;
}
else
{
pushdown(u);
ll mid=(tree[u].l+tree[u].r)>>1;
if(mid>=l)change(u<<1,l,r);
if(mid+1<=r)change(u<<1|1,l,r);
pushup(u);
}
}
ll ask(ll u,ll l,ll r)
{
if(tree[u].l>=l&&tree[u].r<=r)
{
return tree[u].sum;
}
else
{
ll res=0;
pushdown(u);
ll mid=(tree[u].l+tree[u].r)>>1;
if(mid>=l)res+=ask(u<<1,l,r);
if(mid+1<=r)res+=ask(u<<1|1,l,r);
return res;
}
}
signed main()
{
cin>>n>>m;
for(ll i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
while(m--)
{
cin>>opt;
if(opt=='C')
{
cin>>l>>r>>d;
change(1,l,r);
}
else if(opt=='Q')
{
cin>>l>>r;
cout<<ask(1,l,r)<<"\n";
}
}
}
$\color{green} {普通平衡树}$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e4,M=1e3+1e2;
const ll INF=1e18;
ll n;
struct node
{
ll l,r;
ll key,val;
ll cnt,size;
}tr[N];
ll root,idx;
void pushup(ll p)
{
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
ll get_node(ll key)
{
tr[++idx].key=key;
tr[idx].val=rand();
tr[idx].cnt=tr[idx].size=1;
return idx;
}
void zig(ll &p)//右旋
{
ll q=tr[p].l;
tr[p].l=tr[q].r,tr[q].r=p,p=q;
pushup(tr[p].r),pushup(p);
}
void zag(ll &p)
{
ll q=tr[p].r;
tr[p].r=tr[q].l,tr[q].l=p,p=q;
pushup(tr[p].l),pushup(p);
}
void build()
{
get_node(-INF),get_node(INF);
root=1,tr[1].r=2;
pushup(root);
if(tr[1].val<tr[2].val)zag(root);
}
void insert(ll &p,ll key)
{
if(!p)p=get_node(key);
else if(tr[p].key==key)tr[p].cnt++;
else if(tr[p].key>key)
{
insert(tr[p].l,key);
if(tr[tr[p].l].val>tr[p].val)zig(p);
}
else
{
insert(tr[p].r,key);
if(tr[tr[p].r].val>tr[p].val)zag(p);
}
pushup(p);
}
void remove(ll &p,ll key)
{
if(!p)return ;
if(tr[p].key==key)
{
if(tr[p].cnt>1)tr[p].cnt--;
else if(tr[p].l||tr[p].r)
{
if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r,key);
}
else
{
zag(p);
remove(tr[p].l,key);
}
}
else p=0;
}
else if(tr[p].key>key)remove(tr[p].l,key);
else remove(tr[p].r,key);
pushup(p);
}
ll get_rank_by_key(ll p,ll key)
{
if(!p)return 0;
if(tr[p].key==key)return tr[tr[p].l].size+1;
if(tr[p].key>key)return get_rank_by_key(tr[p].l,key);
return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
ll get_key_by_rank(ll p,ll rank)
{
if(!p)return INF;
if(tr[tr[p].l].size>=rank)return get_key_by_rank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank)return tr[p].key;
return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
ll get_prev(ll p,ll key)
{
if(!p)return -INF;
if(tr[p].key>=key)return get_prev(tr[p].l,key);
return max(tr[p].key,get_prev(tr[p].r,key));
}
ll get_next(ll p,ll key)
{
if(!p)return INF;
if(tr[p].key<=key)return get_next(tr[p].r,key);
return min(tr[p].key,get_next(tr[p].l,key));
}
signed main()
{
build();
cin>>n;
while(n--)
{
ll opt,x;
cin>>opt>>x;
if(opt==1)insert(root,x);
else if(opt==2)remove(root,x);
else if(opt==3)cout<<get_rank_by_key(root,x)-1<<"\n";
else if(opt==4)cout<<get_key_by_rank(root,x+1)<<"\n";
else if(opt==5)cout<<get_prev(root,x)<<"\n";
else cout<<get_next(root,x)<<"\n";
}
}
$\color{green} {后缀数组}$
$\color{purple} {倍增求后缀数组}$
$sa[i]:$ 排名第 $i$ 位的是第几个后缀
$rk[i]:$ 第 $i$ 个后缀的排名是多少
$height[i]:$ $sa[i]$ 与 $sa[i-1]$ 的最长公共前缀
用 $lcp(i,j)$ 来表示排名第 $i$ 个后缀和排名第 $j$ 个后缀的最长公共前缀
则
$$lcp(i,i)=len(i)$$
当 $i<j$时，有结论
$$lcp(i,j)=\min(lcp(i,k),lcp(k,j))$$
其中 $i \le k \le j$
所以
$$lcp(i,j)=\min(lcp(i,i+1),lcp(i+1,i+2)…lcp(j-1,j))$$
$$height[i]=lcp(i-1,i)$$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+1e4,M=1e3+1e2;
ll n,m;
char s[N*10];
ll sa[N*10],x[N*10],y[N*10],c[N*10],rk[N*10],height[N*10];
void get_sa()
{
for(ll i=1;i<=n;i++)c[x[i]=s[i]]++;
for(ll i=2;i<=m;i++)c[i]+=c[i-1];
for(ll i=n;i>=1;i--)sa[c[x[i]]--]=i;
for(ll k=1;k<=n;k<<=1)
{
ll num=0;
for(ll i=n-k+1;i<=n;i++)y[++num]=i;
for(ll i=1;i<=n;i++)
if(sa[i]>k)
y[++num]=sa[i]-k;
for(ll i=1;i<=m;i++)c[i]=0;
for(ll i=1;i<=n;i++)c[x[i]]++;
for(ll i=2;i<=m;i++)c[i]+=c[i-1];
for(ll i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=1,num=1;
for(ll i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(num==n)break;
m=num;
}
}
void get_height()
{
for(ll i=1;i<=n;i++)rk[sa[i]]=i;
for(ll i=1,k=0;i<=n;i++)
{
if(rk[i]==1)continue;
if(k)k--;
ll j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
height[rk[i]]=k;
}
}
signed main()
{
scanf("%s",s+1);
n=strlen(s+1),m=122;
get_sa();
get_height();
for(ll i=1;i<=n;i++)cout<<sa[i]<<" ";
cout<<"\n";
for(ll i=1;i<=n;i++)cout<<height[i]<<" ";
}
$\color{red} {图论}$
$\color{green} {二分图}$
bool find(ll l)
{
for(ll i=h[l];i;i=nex[i])
{
ll j=t[i];
if(vist[j])continue;
vist[j]=true;
if(!match[j]||find(match[j]))
{
match[j]=l;
return true;
}
}
return false;
}
