【 模_板 】 for NOIP 2017
2024-08-30 05:12:27
高精度
#include <cstring>
#include <cstdio> #define max(a,b) (a>b?a:b) inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int N(1e5+); namespace Bignum_ {
struct Bignum {
int num[]; // num[0] 表示数字位数 void init() { memset(num,,sizeof(num)); num[]=; } void Mul(int x) // 高精乗低精
{
for(int i=,ove=; i<=num[]; ++i)
{
num[i]=num[i]*x+ove;
if(num[i]>)
{
num[]= max(num[],i+);
ove=num[i]/;
num[i] %=;
}
else ove=;
}
for(; !num[num[]]&&num[]>; ) num[]--;
} void Del(int x) //高精除低精
{
for(int tt,t=,i=num[]; i; --i)
{
tt=num[i];
num[i]=(tt+t*)/x;
t=(t*+num[i])%x;
}
for(; !num[num[]]&&num[]>; ) num[]--;
} void print()
{
for(int i=num[]; i; i--) printf("%d",num[i]);
}
}a,b; Bignum Add(Bignum a,Bignum b) //高精加高精
{
Bignum c; c.num[]=max(a.num[],b.num[]);
for(int x=,i=; i<=c.num[]; ++i)
{
c.num[i]=a.num[i]+b.num[i]+x;
if(c.num[i]>)
{
x=c.num[i]/; c.num[i]%=;
c.num[]=max(c.num[],i+);
}
}
for(; !c.num[c.num[]]&&c.num[]>; ) c.num[]--;
return c;
} inline bool judge(Bignum a,Bignum b)
{
if(a.num[]>b.num[]) return ;
else if(a.num[]<b.num[]) return ;
else for(int i=a.num[]; i; --i)
if(a.num[i]>b.num[i]) return ;
else if(a.num[i]<b.num[i]) return ;
return ;
} Bignum Sub(Bignum a,Bignum b) // 高精-高精
{
Bignum c; bool flag=;
c.num[]=max(a.num[],b.num[]);
if(judge(a,b)) //判谁做减数
for(int x=,i=; i<=c.num[]; ++i)
{
c.num[i]=a.num[i]-b.num[i];
if(c.num[i]<) c.num[i+]--,c.num[i]+=;
}
else
{
for(int x=,i=; i<=c.num[]; ++i)
{
c.num[i]=b.num[i]-a.num[i];
if(c.num[i]<) c.num[i+]--,c.num[i]+=;
}
flag=;
}
for(; !c.num[c.num[]]&&c.num[]>; ) c.num[]--;
if(flag) c.num[c.num[]]=-c.num[c.num[]];
return c;
}
} int Presist()
{ return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
高精度
数论知识
#include <cstring>
#include <cstdio>
#include <cmath> #define LL long long inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
} const int mod(1e9+);
const int N(); bool no_pri[N];
LL fac[N],inv[N];
int cnt,pri[N],phi[N]; namespace Number_Theory { inline LL Mul(LL a,int b,int p) //慢速乗，防乗爆
{
LL ret=;
for(; b; b>>=, a<<=,a%=p)
if(b&) ret+=a, ret%p;
return ret;
} inline LL Pow(LL a,int b,int p) // 快速幂
{
LL ret=;
for(; b; b>>=, a*=a,a%=p)
if(b&) ret*=a, ret%=p;
return ret;
} inline bool judge_ss(int x) // 根x 判素数
{
if(x<) return ;
for(int i=; i*i<=x; ++i)
if(x%i==) return ;
return ;
} inline void Euller(int n) // 欧拉筛素数和欧拉函数
{
/*
(1) 若(N%a==0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;
(2) 若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);
其中a是N的质因数。
关于欧拉函数还有以下性质：
(1) phi[p]=p-1; (p为素数);
(2)若N=p^n(p为素数)，则 phi[N]=(p-1)*p^(n-1);
*/
for(int i=; i<=n; ++i)
{
if(!no_pri[i]) pri[++cnt]=i,phi[i]=i-;
for(int j=; j<=cnt; ++j)
{
if(pri[j]*i>n) break;
no_pri[pri[j]*i]=true;
if(i%pri[j]==)
{
phi[i*pri[j]]=phi[i]*pri[j]; break;
}
else phi[i*pri[j]]=phi[i]*(pri[j]-);
}
}
} inline LL Phi(LL x) // 欧拉函数
{
LL ret=;
for(int i=; i<=x; ++i)
{
if(x%i) continue;
ret*=i-, x/=i;
for(; x%i==; )
ret*=i,x/=i;
}
if(x>) ret*=x-;
return ret;
} inline LL exgcd(LL a,LL b,LL &x,LL &y) // 扩展欧几里得
{
if(!b) { x=,y=; return a;}
LL ret=exgcd(b,a%b,x,y),tmp=x;
x=y; y=tmp-a/b*y; return ret;
} inline LL Fermat(LL a,LL p) // p为素数 费马小定理 a^(p-1) = 1 mod p
{
return Pow(a,p-,p); // 逆元
} inline LL Pre_inv(int p) // a/b%mod --> a*inv(b,mod)
{
fac[]=fac[]=inv[]=;
for(int i=; i<N; ++i)
{
fac[i]=1ll*fac[i-]%p*i%p;
inv[i]=1ll*inv[p%i]*(p-p/i)%p; //线性求逆元
/* 拓展欧几里得求逆元
LL x,y,gcd=exgcd(i,mod,x,y);
inv[i]= gcd==1 ?(x+mod)%mod :-1;
*/
/* 欧拉函数求逆元
Euller();
inv[i]=Fermat(i,mod);
*/
}
} inline LL CRT(LL *m,LL *p,int n) //中国剩余定理，互质不互质情况
{
LL x,y,tmp,gcd,b,c;
LL ret=m[],a=p[],mod;
for(int i=; i<=n; ++i)
{
tmp=m[i],b=p[i],c=tmp-ret;
gcd=exgcd(a,b,x,y);
if(c%gcd) return -;
x*=c/gcd, mod=b/gcd;
for(x+=mod; x>=mod; ) x-=mod;
ret+=a*x, a*=mod;
}
return ret?ret:(ret+a);
} struct Matrix_fb { // 矩阵优化菲波那切数列
LL e[][];
void init_base()
{
e[][]=;
e[][]=;
e[][]=;
e[][]=;
}
void init_ans()
{
e[][]=e[][]=;
e[][]=e[][]=;
}
Matrix_fb operator * (Matrix_fb x) const
{
Matrix_fb ret;
for(int i=; i<; ++i)
for(int j=; j<; ++j)
{
ret.e[i][j]=;
for(int k=; k<; ++k)
ret.e[i][j]+=e[i][k]*x.e[k][j],ret.e[i][j]%=mod;
}
return ret;
}
}ans,base; inline LL Fibonacci(int n)
//斐波那契数列 gcd( f[a],f[b] )= f[ gcd(a,b) ], f[i]=f[i-1]+f[i-2]
{
double x=sqrt(5.0);
return pow(((+x)/),n)/x - pow(((-x)/),n)/x; // 通式
if(n==||n==) return ;
for( n-=; n; n>>=,base=base*base)
if(n&) ans=ans*base;
return ans.e[][];
}
} // 排列组合
namespace Permutations { inline void Pre_C(int n,int p) // 预处理组合数
{
LL C[n][n];
memset(C,,sizeof(C));
for(int i=; i<n; ++i)
{
C[i][i]=C[i][]=;
for(int j=; j<i; ++j)
C[i][j]=(C[i-][j]+C[i-][j-])%p;
}
} LL C(LL n,LL m,LL p)
{
if(m>n) return ;
LL t1=Number_Theory::Fermat(fac[m],p);
LL t2=Number_Theory::Fermat(fac[n-m],p);
return fac[n]%p*t1%p*t2%p;
} LL Luc(LL n,LL m,LL p)
{
if(n<m) return ;
if(m==) return ;
return (C(n%p,m%p,p))*Luc(n/p,m/p,p)%p;
} inline void Use_luc(int n,int m,int p)
// Lucas定理 Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)
{
Number_Theory:: Pre_inv(p);
printf("%lld\n",Luc(n,m,p));
} inline int Catelan(int n) //卡特兰数
{
int h[n]; memset(h,,sizeof(h));
h[]=h[]=;
for(int i=; i<=n; ++i)
for(int j=; j<=i; ++j)
h[i]=h[i-j]*h[j-]+h[i];
return h[n];
} inline int stirling(int n,int m)
{
/*
stirling数，递推公式s[i][j]=s[i-1][j]*j+s[i-1][j-1]
S(p,k)的一个组合学解释是：
将p个物体划分成k个非空的不可辨别的（可以理解为盒子没有编号）集合的方法数。
k!S(p,k)是把p个人分进k间有差别(如：被标有房号）的房间(无空房）的方法数。
S(p,k)的递推公式是：S(p,k)=k*S(p-1,k)+S(p-1,k-1) ,1<= k<=p-1
边界条件：S(p,p)=1 ,p>=0 S(p,0)=0 ,p>=1
递推关系的说明：
考虑第p个物品，p可以单独构成一个非空集合，此时前p-1个物品构成k-1个非空的不可辨别的集合，方法数为S(p-1,k-1)；
也可以前p-1种物品构成k个非空的不可辨别的集合，第p个物品放入任意一个中，这样有k*S(p-1,k)种方法。
注意：当m>n||m==0时直接输出0,！
*/
int s[n][n]; memset(s,,sizeof(s));
for(int i=; i<=n; ++i) s[i][i]=;
for(int i=; i<=n; ++i)
for(int j=; j<=i; ++j)
s[i][j]=s[i-][j-]+s[i-][j]*j;
return (!m||m>n)?:s[n][m];
}
} int Presist()
{ return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
数论知识
图论知识
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue> #define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b) inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int INF(0x3f3f3f3f);
const int N(1e5+);
const int M(1e6+); // Graph_theory int sumedge,head[N]; struct Edge {
int v,next,w;
Edge(int v=,int next=,int w=):v(v),next(next),w(w){}
}edge[M<<]; inline void ins(int u,int v,int w)
{
edge[++sumedge]=Edge(v,head[u],w),head[u]=sumedge;
edge[++sumedge]=Edge(u,head[v],w),head[u]=sumedge;
} namespace The_short_circuit {
inline void Floyd(int n,int m)
{
int dis[][];
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j)
dis[i][j]=INF*(i!=j); for(int k=; k<=n; ++k)
for(int i=; i<=n; ++i)
for(int j=; j<=n; ++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
} int dis[N];
bool inq[N],vis[N]; inline void SPFA(int s,int n)
{
std::queue<int>que;
for(int i=; i<=n; ++i)
inq[i]=, dis[i]=INF;
dis[s]=; que.push(s);
for(int u,v; !que.empty(); )
{
u=que.front(); que.pop(); inq[u]=;
for(int i=head[u]; i; i=edge[i].next)
{
v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
if(!inq[v]) que.push(v),inq[v]=;
}
}
}
} struct Node {
int pos,dis;
bool operator < (const Node&x)const
{
return dis>x.dis;
}
}u,v; inline void Dijkstra(int s,int n)
{
std::priority_queue<Node>que;
for(int i=; i<=n; ++i)
vis[i]=, dis[i]=INF;
u.dis=dis[s]=, u.pos=s; que.push(u);
for(; !que.empty(); )
{
u=que.top(); que.pop();
if(vis[u.pos]) continue;
for(int i=head[u.pos]; i; i=edge[i].next)
{
v.pos=edge[i].v;
if(dis[v.pos]>dis[u.pos]+edge[i].w)
{
dis[v.pos]=dis[u.pos]+edge[i].w;
v.dis= dis[v.pos]; que.push(v);
}
}
}
}
} namespace Negative_ring {
bool vis[N];
int dis[N];
bool DFS(int u)
{
vis[u]=;
for(int v,i=head[u]; i; i=edge[i].next)
{
v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
if(vis[v]||DFS(u))
{
vis[v]=;
return ;
}
}
}
return vis[u]=;
}
} namespace Tarjan_ { int sumcol,col[N];
int tim,dfn[N],low[N];
int stack[N],instack[N],top;
int cutpoint[N],cutedge[M]; void DFS(int u) //强联通分量，无向图加一个pre判断
{
low[u]=dfn[u]=++tim;
stack[++top]=u, instack[u]=;
for(int v,i=head[u]; i; i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v]) DFS(v), low[u]=min(low[u],low[v]);
else if(instack[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
col[u]=++sumcol;
for(; stack[top]!=u; top--)
{
col[stack[top]]=sumcol;
instack[stack[top]]=false;
}
instack[u]=, top--;
}
} void Tarjan(int u,int pre) //sumedge=-1 双联通
{
int sumtredge=; bool if_cutpoint=;
low[u]=dfn[u]=++tim;
for(int v,i=head[u]; i; i=edge[i].next)
{
if((i^)==pre) continue;
if(!dfn[v])
{
sumtredge++; Tarjan(v,i);
if(low[v]>=dfn[u]) if_cutpoint=;
if(low[v]>dfn[u]) cutedge[i>>]=;
low[u]=min(low[u],low[v]);
}
else low[u]=min(low[u],dfn[v]);
}
if(!pre)
{
if(sumtredge>) cutpoint[u]=;
}
else if(if_cutpoint) cutpoint[u]=;
} inline void work(int n)
{
tim=;sumcol=;top=;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(stack,,sizeof(stack));
memset(instack,,sizeof(instack)); for(int i=; i<=n; ++i)
if(!dfn[i]) DFS(i);
Tarjan(,);
}
} namespace MST_ { struct Edge {
int u,v,w;
bool operator < (const Edge&x)const
{
return w<x.w;
}
} road[M];
int fa[N]; int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } inline void Kruskar(int m,int n)
{
for(int i=; i<=n; ++i) fa[i]=i;
std:: sort(road+,road+m+);
int cnt=, ret=;
for(int fx,fy,i=; i<=m; ++i)
{
fx=find(road[i].u),fy=find(road[i].v);
if(fx==fy) continue; fa[fx]=fy;
ret+=road[i].w; if(++cnt==n-) break;
}
printf("%d\n",ret);
} inline void Prim(int n)
{
int ret=,minn,vis[N],dis[N/][N/],d[N];
for(int i=; i<=n; ++i) vis[i]=,d[i]=dis[][i];
vis[]=;
for(int u,i=; i<=n; ++i)
{
minn=INF;
for(int j=; j<=n; ++j)
if(!vis[j]&&minn>d[j]) minn=d[u=j];
if(minn=INF) break;
ret+=minn; vis[u]=;
for(int v=; v<=n; ++v)
if(!vis[v]&&d[v]>dis[u][v]) d[v]=dis[u][v];
}
printf("%d\n",ret);
} } namespace Bisection_Graph { inline bool check(int s)
{
int col[N]; memset(col,-,sizeof(col));
col[s]=; std::queue<int>que; que.push(s);
for(int u,v; !que.empty(); )
{
u=que.front(); que.pop();
for(int i=head[u]; i; i=edge[i].next)
{
v=edge[i].v;
if(col[v]==-)
{
col[v]=col[u]^;
que.push(v);
}
else if(col[v]==col[u]) return ;
}
}
return true;
} int match[N],map[N/][N/];
int sumvis,vis[N];
bool Get(int u,int n)
{
for(int v=; v<=n; ++v)
if(map[u][v]&&vis[v]!=sumvis)
{
vis[v]=sumvis;
if(!match[v]||Get(match[v],n))
{
match[v]=u;
return true;
}
}
return false;
}
inline void Hungarian(int n)
{
int ans=;
for(int i=; i<=n; ++i)
sumvis++,ans+=Get(i,n);
printf("%d\n",ans);
}
} namespace Top_sort_ {
inline void work(int n,int *rd)
{
std::queue<int>que;
for(int i=; i<=n; ++i)
if(!rd[i]) que.push(i);
for(int u,v; !que.empty(); )
{
u=que.front(); que.pop();
for(int i=head[u]; i; i=edge[i].next)
if(--rd[edge[i].v]==) que.push(edge[i].v);
}
}
} int Presist()
{ return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
图论知识
数据结构
#include <cstring>
#include <cstdio> #define swap(a,b) {int c=a;a=b;b=c;}
#define max(a,b) (a>b?a:b) inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int N(1e5+); /*
Data_structure
*/ int sum[N];
namespace Tree_array {
#define lowbit(x) (x&((~x)+1))
inline void Update(int i,int x)
{
for(; i<N; i+=lowbit(i)) sum[i]+=x;
}
inline int Query(int i)
{
int ret=;
for(; i; i-=lowbit(i)) ret+=sum[i];
return ret;
}
} struct Tree {
bool flag;
int l,r,mid,val;
}tr[N<<];
namespace Line_segment_tree { #define lc (now<<1)
#define rc (now<<1|1)
#define mid (tr[now].l+tr[now].r>>1) void Update(int now)
{
tr[now].val=tr[lc].val+tr[rc].val;
} void Build(int now,int l,int r)
{
tr[now].l=l, tr[now].r=r;
if(l==r)
{
read(tr[now].val);
tr[now].flag=; return ;
}
Build(lc,l,mid),Build(rc,mid+,r);
Update(now);
} void Pushdown(int now)
{
tr[lc].flag+=tr[now].flag;
tr[lc].val+=tr[now].flag*(tr[lc].r-tr[lc].l+);
tr[rc].flag+=tr[now].flag;
tr[rc].val+=tr[now].flag*(tr[rc].r-tr[rc].l+);
tr[now].flag=;
} void Change1(int now,int to,int x)
{
if(tr[now].l==tr[now].r)
{
tr[now].val=+x;
tr[now].flag+=x;
return ;
}
if(tr[now].flag) Pushdown(now);
if(to<=mid) Change1(lc,to,x);
else Change1(rc,to,x);
Update(now);
} void Change2(int now,int l,int r,int x)
{
if(tr[now].l==l&&tr[now].r==r)
{
tr[now].val+=x*(tr[now].r-tr[now].l+);
tr[now].flag+=x; return ;
}
if(tr[now].flag) Pushdown(now);
if(r<=mid) Change2(lc,l,r,x);
else if(l>mid) Change2(rc,l,r,x);
else Change2(lc,l,mid,x),Change2(rc,mid+,r,x);
Update(now);
} int Query(int now,int l,int r)
{
if(tr[now].l==l&&tr[now].r==r) return tr[now].val;
if(tr[now].flag) Pushdown(now);
if(r<=mid) return Query(lc,l,r);
else if(l>mid) return Query(rc,l,r);
else return Query(lc,l,mid)+Query(rc,mid+,r);
Update(now);
}
} int st[N][],log2[N],t=;
namespace ST_ {
inline void wokr(int n)
{
for(int i=; i<=n; ++i)
read(st[i][]),log2[i]=(<<t+==i?++t:t);
for(int j=; <<j<=n; ++j)
for(int i=; i+(<<j)<=n+; ++i)
st[i][j]=max(st[i][j-],st[i+(<<j-)][j-]);
}
} int head[N],sumedge;
struct Edge {
int v,next;
}edge[N<<]; int size[N],dep[N];
namespace LCA_1 {
int dad[N],son[N],top[N];
void DFS(int u,int depth)
{
size[u]=;dep[u]=depth;
for(int v,i=head[u]; i; i=edge[i].next)
{
v=edge[i].v;
if(dad[u]==v) continue; dad[v]=u;
DFS(v,depth+), size[u]+=size[v];
if(size[son[u]]<size[v]) son[u]=v;
}
} void DFS_(int u,int Top)
{
top[u]=Top; if(son[u]) DFS_(son[u],Top);
for(int v,i=head[u]; i; i=edge[i].next)
{
v=edge[i].v;
if(v!=son[u]&&v!=dad[u]) DFS_(v,v);
}
} inline int LCA(int x,int y)
{
for(; top[x]!=top[y]; x=dad[top[x]])
if(dep[top[x]]<dep[top[y]]) swap(x,y);
return dep[x]<dep[y]?x:y;
} } namespace LCA_2 {
int dad[N][]; void DFS(int u,int fa)
{
dep[u]=dep[fa]+;
for(int i=; dad[u][i-]; ++i)
dad[u][i]=dad[dad[u][i-]][i-];
for(int v,i=head[u]; i; i=edge[i].next)
if(!dep[edge[i].v]) dad[edge[i].v][]=u,DFS(v,u);
} int LCA(int x,int y)
{
if(dep[x]>dep[y]) swap(x,y);
for(int i=; i>=; --i)
if(dep[dad[y][i]]>dep[dad[x][i]]) y=dad[y][i];
if(x==y) return x;
for(int i=; i>=; --i)
if(dad[x][i]!=dad[y][i]) x=dad[x][i],y=dad[y][i];
return dad[x][];
}
} namespace Dai_quan_bing_cha_ji {
int fa[N],val[N];
int find(int x)
{
if(fa[x]==x) return x;
int dad=find(fa[x]);
val[x]+=val[fa[x]];
return fa[x]=dad;
}
inline void combine(int x,int y)
{
x=find(x),y=find(y);
if(x!=y) val[x]+=val[y],fa[x]=y;
}
} int trie[N<<][],tot;
namespace Trie_Tree {
inline void Build(char *s)
{
int len=strlen(s),now=;
for(int x,i=; i<len; ++i)
{
x=s[i]-'a'+;
if(trie[now][x])
now=trie[now][x],trie[now][]++;
else now=trie[now][x]=++tot,trie[now][]++;
}
}
inline int find(char *s)
{
int len=strlen(s),now=,p=;
for(; p<len; )
if(trie[now][s[p]-'a'+])
now=trie[now][s[p]-'a'+],++p;
else return ;
return trie[now][];
}
} namespace The_monotonous_queue {
int que[N],head=,tail,a[N]; inline void work(int n,int m)
{
for(int i=; i<=n; ++i)
{
read(a[i]);
for(; head<=tail&&a[que[tail]]<=a[i]; ) tail--;
for(que[++tail]=i; head<=tail&&i>m; ) head++;
}
}
} int Presist()
{ return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
数据结构
字符串
#include <cstring>
#include <cstdio> const int N(1e6+); char s[N],a[N];
int p[N]; namespace Kmp {
inline void Get_next(char *s)
{
int len=strlen(s+);
for(int j=,i=; i<=len; p[i++]=j)
{
for(; j&&s[i]!=s[j+]; ) j=p[j];
if(s[i]==s[j+]) j++;
}
}
// 字符串最短长度 len-p[len]
inline void kmp(char *a,char *s)
// 匹配子串位置
{
Get_next(s);
int la=strlen(a+),ls=strlen(s+);
for(int j=,i=,k=; i<=la; ++i)
{
for(; j&&a[i]!=s[j+]; ) j=p[j];
if(a[i]==s[j+]) j++;
if(j==ls) printf("%d\n",i-j+),j=p[j];
}
}
} #define ull unsigned long long
const int P(); ull hs1[],hs2[]; namespace Hash_ {
inline ull Pow(ull a,int b)
{
ull ret=;
for(; b; b>>=,a*=a)
if(b&) ret*=a;
return ret;
} inline bool Compare(int l,int r)
{
return hs1[r]-hs1[l]*Pow(P,r-l+)==hs2[r-l+];
} inline void Get_hash(char *s)
{
int len=strlen(s+);
for(int i=; i<=len; ++i)
hs1[i]=hs1[i-]*P+s[i]-'a';
}
} int Presist()
{ return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}
字符串
最新文章
- BDYY【面试题】
- modelsim无法识别include文件的解决方法
- 《深入.NET平台和C#编程》--题型释疑
- Java基础-数据类型转换
- iOS Foundation框架 -3.利用NSNumber和NSValue将非OC对象类型数据存放到集合
- IE8的Textarea滚动条乱跳的解决方案
- 关于添加非系统framework后，import导入头文件时没有提示的解决办法
- java基础知识再学习--集合框架-对象的强、软、弱和虚引用
- onclick=‘’return false“
- c语言，递归翻转一个单链表，c实现单链表
- zend笔记
- KoaHub.js是基于 Koa.js 平台的 Node.js web 快速开发框架
- threejs里面的vector3源码解析
- 201521123117 《Java程序设计》第5周学习总结
- redis学习笔记01 — 基本介绍、安装配置及常用命令
- java微信公众号JSAPI支付以及所遇到的坑
- ant design Modal关闭时清除数据的解决方案
- java 对mongodb的操作
- Kettle转换或作业乱码
- Mysql 简单的使用定时器调用存储过程