muuuuuuban
快要考省选了 模板还没打 趁还有3天加油干。。。
1.MTT
//MTT
#include<bits/stdc++.h>
#define mod1 469762049
#define mod2 998244353
#define mod3 1004535809
#define N 300005
#define ll long long
using namespace std;
int a[N],b[N],mod,ans[3][N],rev[N],n,m,c[N],d[N];
inline int read()
{
int ans=0,f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
return ans*f;
}
inline int mul(int a,int b,int mod)
{
int ans=1;
while(b)
{
if(b&1) ans=(ll)ans*a%mod;
a=(ll)a*a%mod;
b>>=1;
}
return ans;
}
inline void NTT(int n,int a[],int dft,int mod)
{
for(int i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
for(int k=1;k<n;k<<=1)
for(int i=0,wn=mul(3,(mod-1)/(k<<1),mod);i<n;i+=(k<<1))
for(int j=i,wnk=1;j<i+k;++j,wnk=(ll)wnk*wn%mod)
{
int x=a[j],y=(ll)wnk*a[j+k]%mod;
a[j]=(x+y)%mod,a[j+k]=(x-y+mod)%mod;
}
if(dft==-1)
{
int inv=mul(n,mod-2,mod);
a[0]=(ll)a[0]*inv%mod;
for(int i=1;i<=n/2;++i)
{
a[i]=(ll)a[i]*inv%mod;
if((i<<1)!=n) a[n-i]=(ll)a[n-i]*inv%mod;
swap(a[i],a[n-i]);
}
}
}
int inv_1=mul(mod1,mod2-2,mod2),inv_1_2=mul((ll)mod1*mod2%mod3,mod3-2,mod3);
inline int get(int x)
{
ll k=(ll)ans[0][x]+(ll)(ans[1][x]-ans[0][x]+mod2)%mod2*inv_1%mod2*mod1;
return ((ll)(ans[2][x]-k%mod3+mod3)%mod3*inv_1_2%mod3*((ll)mod1*mod2%mod)%mod+k)%mod;
}
signed main()
{
n=read()+1,m=read()+1,mod=read();
for(int i=0;i<n;++i) a[i]=read();
for(int i=0;i<m;++i) b[i]=read();
int lim=1,l=0;
while(lim<n+m) lim<<=1,l++;
for(int i=0;i<lim;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
copy(a,a+lim,c);
copy(b,b+lim,d);
NTT(lim,c,1,mod1);NTT(lim,d,1,mod1);
for(int i=0;i<lim;++i) ans[0][i]=(ll)c[i]*d[i]%mod1;
NTT(lim,ans[0],-1,mod1);
copy(a,a+lim,c);
copy(b,b+lim,d);
NTT(lim,c,1,mod2);NTT(lim,d,1,mod2);
for(int i=0;i<lim;++i) ans[1][i]=(ll)c[i]*d[i]%mod2;
NTT(lim,ans[1],-1,mod2);
copy(a,a+lim,c);
copy(b,b+lim,d);
NTT(lim,c,1,mod3);NTT(lim,d,1,mod3);
for(int i=0;i<lim;++i) ans[2][i]=(ll)c[i]*d[i]%mod3;
NTT(lim,ans[2],-1,mod3);
for(int i=0;i<n+m-1;++i)
printf("%lld ",get(i));
}2.多项式求逆
#include<bits/stdc++.h>
#define N 300005
#define p 998244353
#define ll long long
using namespace std;
int a[N],n,b[N],c[N],rev[N];
inline int read()
{
int ans=0,f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
return ans*f;
}
inline int mul(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=(ll)ans*a%p;
a=(ll)a*a%p;
b>>=1;
}
return ans;
}
inline void NTT(int n,int a[],int dft)
{
for(int i=0;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
for(int k=1;k<n;k<<=1)
for(int i=0,wn=mul(3,(p-1)/(k<<1));i<n;i+=(k<<1))
for(int j=i,wnk=1;j<i+k;++j,wnk=(ll)wnk*wn%p)
{
int x=a[j]%p,y=(ll)a[j+k]*wnk%p;
a[j]=(x+y)%p,a[j+k]=(x-y+p)%p;
}
if(dft==-1)
{
int inv=mul(n,p-2);
reverse(a+1,a+n);
for(int i=0;i<n;++i) a[i]=(ll)a[i]*inv%p;
}
}
void work(int n,int a[],int b[])
{
if(n==1){b[0]=mul(a[0],p-2);return;}
work((n+1)>>1,a,b);
int lim=1,l=0;
while(lim<(n<<1)) lim<<=1,l++;
for(int i=1;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
for(int i=0;i<n;++i) c[i]=a[i];
for(int i=n;i<lim;++i) c[i]=0;
NTT(lim,c,1),NTT(lim,b,1);//for(int i=0;i<n;++i) printf("%d ",rev[i]);puts("");
for(int i=0;i<lim;++i) b[i]=(ll)(2ll-(ll)c[i]*b[i]%p+p)%p*b[i]%p;
NTT(lim,b,-1);
for(int i=n;i<lim;++i) b[i]=0;
}
int main()
{
n=read();
for(int i=0;i<n;++i) a[i]=read();
work(n,a,b);
for(int i=0;i<n;++i) printf("%d ",b[i]);
}
3.分治NTT
#include<bits/stdc++.h>
#define N 300005
#define ll long long
#define p 998244353
using namespace std;
int n,g[N],f[N],rev[N],a[N],b[N];
inline int read()
{
int ans=0,f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
return ans*f;
}
inline int mul(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=(ll)ans*a%p;
a=(ll)a*a%p;
b>>=1;
}
return ans;
}
inline void NTT(int n,int a[],int dft)
{
for(int i=1;i<n;++i) if(rev[i]>i) swap(a[i],a[rev[i]]);
for(int k=1;k<n;k<<=1)
for(int i=0,wn=mul(3,(p-1)/(k<<1));i<n;i+=(k<<1))
for(int j=i,wnk=1;j<i+k;++j,wnk=(ll)wnk*wn%p)
{
int x=a[j],y=(ll)wnk*a[j+k]%p;
a[j]=(x+y)%p,a[j+k]=(x-y+p)%p;
}
if(dft==-1)
{
int inv=mul(n,p-2);
reverse(a+1,a+n);
for(int i=0;i<n;++i) a[i]=(ll)a[i]*inv%p;
}
}
void work(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
work(l,mid);
int len=0,lim=1,n=r-l+1;
while(lim<(n+mid-l+1)) lim<<=1,len++;
for(int i=1;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));
for(int i=0;i<(mid-l+1);++i) a[i]=f[i+l];
for(int i=mid-l+1;i<lim;++i) a[i]=0;
// for(int i=0;i<mid-l+1;++i) printf("%d ",a[i]);puts("");
for(int i=0;i<n;++i) b[i]=g[i];
for(int i=n;i<lim;++i) b[i]=0;
NTT(lim,a,1),NTT(lim,b,1);
for(int i=0;i<lim;++i) a[i]=(ll)a[i]*b[i]%p;
NTT(lim,a,-1);
// for(int i=0;i<n;++i) printf("%d ",a[i]);puts("");
for(int i=mid-l+1;i<n;++i) f[i+l]=(f[i+l]+a[i])%p;
work(mid+1,r);
}
int main()
{
f[0]=1;
n=read();
for(int i=1;i<n;++i) g[i]=read();
work(0,n-1);
for(int i=0;i<n;++i) printf("%d ",f[i]);
}
4.最小圆覆盖
#include<bits/stdc++.h>
#define N 100005
#define eps 1e-10
#define ld long double
using namespace std;
int n;
ld r;
struct node{ld x,y;ld operator * (const node b) const {return x*b.x+y*b.y;};}a[N],o;
node operator - (const node a,const node b){return (node){a.x-b.x,a.y-b.y};}
node operator + (const node a,const node b){return (node){a.x+b.x,a.y+b.y};}
inline int read()
{
int ans=0,f=1;char c=getchar();
while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
return ans*f;
}
inline ld dis(node a,node b){return sqrt((a-b)*(a-b));}
inline void tt(node a,node b,node c)
{
ld A=a.x-b.x;
ld B=a.y-b.y;
ld C=a.x-c.x;
ld D=a.y-c.y;
ld E=(a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)/2.0;
ld F=(a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)/2.0;
o=(node){(E*D-B*F)/(A*D-B*C),(C*E-A*F)/(B*C-A*D)};
r=dis(o,a);
}
inline bool check(node a)
{
return dis(a,o)>r+eps;
}
int main()
{
n=read();
double x,y;
for(int i=1;i<=n;++i) scanf("%lf %lf",&x,&y),a[i]=(node){x,y};
random_shuffle(a+1,a+1+n);
o=a[1];
for(int i=2;i<=n;++i)
if(check(a[i]))
{
o=a[i],r=0;
for(int j=1;j<i;++j)
if(check(a[j]))
{
o=a[i]+a[j];
o=(node){o.x/2.0,o.y/2.0};
r=dis(a[i],a[j])/2.0;
for(int k=1;k<j;++k)
if(check(a[k]))
{
tt(a[i],a[j],a[k]);
}
}
}
printf("%.10lf\n%.10lf %.10lf",(double)r,(double)o.x,(double)o.y);
}
5.后缀树
#include<bits/stdc++.h>
#define N 1000005
#define inf 1000000000
using namespace std;
int to[N<<1][27],len[N<<1],n,nxt[N<<1],tot,st[N<<1],up;
long long ans,cnt[N<<1];
char s[N],s1[N];
inline int add(int sta,int l)
{
tot++;
st[tot]=sta;
len[tot]=l;
return tot;
}
long long dfs(int x,int l)
{
if(len[x]>=inf-n) cnt[x]=1;
for(int i=0;i<=26;++i)
if(to[x][i])
{
cnt[x]+=dfs(to[x][i],l+len[to[x][i]]);
}
if(cnt[x]>1) ans=max(ans,(long long)l*cnt[x]);
return cnt[x];
}
int main()
{
scanf("%s",s+1);
len[0]=inf;
n=strlen(s+1);
int lst=0,now=0,res=0;s[++n]='z'+1;
for(int i=1;i<=n;++i)
{
res++;lst=0;
while(res)
{
while(len[to[now][s[i-res+1]-'a']]<res) res-=len[now=to[now][s[i-res+1]-'a']];
int ed=s[i-res+1]-'a';
int &v=to[now][ed];
int c=s[st[v]+res-1]-'a';
if(!v)
{
v=add(i-res+1,inf);
nxt[lst]=now;
lst=now;
}
else if(c==s[i]-'a')
{
nxt[lst]=now;
lst=now;
break;
}
else
{
int u=add(st[v],res-1);
to[u][s[i]-'a']=add(i,inf);
to[u][c]=v;
st[v]=st[v]+res-1;
len[v]=len[v]-res+1;
nxt[lst]=v=u,lst=v;
}
if(!now) res--;
else now=nxt[now];
}
}
dfs(0,0);
printf("%lld",ans);
}