LYOI#303. 「2017 山东一轮集训 Day1」Sum

求有多少 n 位十进制数是 p 的倍数且每位之和小于等于? i (0 <= i <= m)，允许前导 0，答案对 998244353取模。

想法：先来个大暴力：$F[i][j][k]$表示i位，模p为j，各位之和为k的个数。转移：$F[i][j][k]->F[i-1][(j*10+l)\%p][k+l]$。

还可以这样表示：$F[x*2] [(j*10^y+l)\%p] [a+b] = F[x][j][a]* F[x][l][b] $。可以先倍增得到$F[1],F[2],F[4]....F[2^n]$，然后依次乘起来。第三维的转移是一个卷积形式，可以用NTT优化。

于是倍增+NTT解决。

Code $O(\log n*m*max(\log m,p^2))$

#include < cstdio >#include < algorithm >#define gec     getchar#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG   fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__);typedef long long ll;templateinline void read(T&x){	x=0;bool f=0;char c=gec();	for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘);	for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘;	x=f?-x:x;}const int LEM(4100),MP(998244353),g(3);int n,m,p; void inc(int &x,int y){x+=y;x-=x>=MP?MP:0;}void dec(int &x,int y){x-=y;x+=x<  0?MP:0;}int min(int a,int b){return a>b?b:a;}namespace NTT{	int W[LEM],R[LEM],wn,il,l,h;		int power(int a,int b)	{		b+=b<0?MP-1:0;int t=1;		for(;b;b>>=1){if(b&1)t=(ll)t*a%MP;a=(ll)a*a%MP;}		return t;	}	void swap(int &a,int &b){int t(a);a=b;b=t;}		void Pretreat(int len)	{		h=0;l=1;while(l<=len+len+1)l<<=1,h++; W[0]=1;		for(int i=1;i<l;i++)R[i]=R[i>>1]>>1|(i&1)<<(h-1);		il=power(l,MP-2);	}		void Tranform(int l,int *a,int ty)	{		for(int i=0;i<l;i++)			if(i>R[i])swap(a[i],a[R[i]]);		for(int leng=2;leng<=l;leng<<=1)		{			int M=leng>>1;			wn=power(g,(MP-1)/leng*ty);			for(int j=1;j<M;j++)W[j]=(ll)W[j-1]*wn%MP;			for(int i=0;i<l;i+=leng)			{				for(int j=0;j<M;j++)				{					int x=a[i+j],y=(ll)a[i+j+M]*W[j]%MP;					a[i+j]=x+y;  a[i+j+M]=x-y;					a[i+j  ]-=a[i+j]>=MP?MP:0;					a[i+j+M]+=a[i+j+M]<0?MP:0;							}			}		}	}		void DFT(int *a)	{		Tranform(l,a,1);	}		void IDFT(int *a)	{		Tranform(l,a,-1);		for(int i=0;i<l;i++)a[i]=(ll)a[i]*il%MP;	}	}void Run(){	int y=10%p,limt=NTT::l;	int F[p][limt],G[p][limt],T[p][limt];	memset(F,0,sizeof(F)); memset(G,0,sizeof(G)); memset(T,0,sizeof(T));	F[0][0]=1; for(int j=min(9,m);~j;j--) G[j%p][j]++;//if (j>m&&j<l) GG	for(;n;n>>=1)	{		if(n&1)		{			memset(T,0,sizeof(T));			for(int i=0;i<p;i++)NTT::DFT(F[i]),NTT::DFT(G[i]);			for(int j=0;j<p;j++)			 for(int l=0;l<p;l++)		  	 {				int Nex=(j*y+l)%p;		 		for(int i=0;i<limt;i++) inc(T[Nex][i],(ll)F[j][i]*G[l][i]%MP);			 }			for(int i=0;i<p;i++)NTT::IDFT(T[i]),NTT::IDFT(G[i]);			memcpy(F,T,sizeof(F));			for(int i=0;i<p;i++)for(int j=m+1;j<limt;j++)F[i][j]=0;		}		memset(T,0,sizeof(T));		for(int i=0;i<p;i++)NTT::DFT(G[i]);		for(int j=0;j<p;j++)		 for(int l=0;l<p;l++)		 {			int Nex=(j*y+l)%p;			for(int i=0;i<limt;i++) inc(T[Nex][i],(ll)G[j][i]*G[l][i]%MP);//多项式加法也可以用点值加。	 	 }		for(int i=0;i<p;i++)NTT::IDFT(T[i]);		memcpy(G,T,sizeof(G));  y=(ll)y*y%p;		for(int i=0;i<p;i++)for(int j=m+1;j<limt;j++)G[i][j]=0;	}	for(int i=0;i<=m;i++)printf("%d ",F[0][i]),inc(F[0][i+1],F[0][i]);	}//O(logn*m*max(logm,p^2))int main(){#ifndef ONLINE_JUDGE	FILE("C");#endif			read(n);read(p);read(m);	NTT::Pretreat(m);	Run();	return 0;}

LYOI#304. 「2017 山东一轮集训 Day1」Set

#include < cstdio >#define gec     getchar#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG   fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__);typedef long long ll;templateinline void read(T&x){	x=0;bool f=0;char c=gec();	for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘);	for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘;	x=f?-x:x;}const int MAXN(100010);int n;ll x[MAXN],all;struct Linear_Base{	ll g[63];	void ins(ll x,ll limt)	{		for(int j=62;~j;j--)		if(((x>>j)&1)&&(!((limt>>j)&1)))		{			if(!g[j]){g[j]=x;return;}//一个数不能被放入两次			else x^=g[j];		}//优先选择0可以放1的		for(int j=62;~j;j--)		if(((x>>j)&1)&&((limt>>j)&1))		{			if(!g[j]){g[j]=x;return;}//一个数不能被放入两次			else x^=g[j];		}//对于相同的优先放1	}		ll Get_Max(ll x)	{		ll val=0;		for(int j=62;~j;j--)		if((!((x>>j)&1))&&(!((val>>j)&1)))			if(g[j])val^=g[j];		for(int j=62;~j;j--)		if(((x>>j)&1)&&(!((val>>j)&1)))			if(g[j])val^=g[j];//求x==1 是否能放1,贪心的放高位		return val;	}}G;ll x1,x2;int main(){#ifndef ONLINE_JUDGE	FILE("C");#endif			read(n);all=0;	for(int i=1;i<=n;i++)read(x[i]),all^=x[i];	for(int i=1;i<=n;i++)G.ins(x[i],all);	x2=G.Get_Max(all);	x1=all^x2;	printf("%lld\n",x1);	return 0;}

LYOI#306. 「2017 山东一轮集训 Day2」Pair

给出一个长度为 n 的数列 {$a_i$} 和一个长度为 m 的数列 {$b_i$}，求 {$a_i$} 有多少个长度为 m 的连续子数列能与 {$b_i$} 匹配。两个数列可以匹配，当且仅当存在一种方案，使两个数列中的数可以两两配对，两个数可以配对当且仅当它们的和不小于 h。

想法：$a_i+b_i \ge h <==> a_i \ge h- b_i$。令$B_i=h-b_i$后，就可以得到一个贪心做法，将两个要匹配的数列排序，一一配对，配对不上就匹配失败。然后快速判断，就可以将他们按权值大小插入一个数列里，令{$a_i$}中数为右括号，{$B_i$}中的数为左括号。一一配对等价于所有括号匹配上了。一个括号序列匹配的充要条件就是任何一个前缀左括号数大于等于右括号数。令左括号为1，右括号为-1，若一个前缀小于0，就说明不能匹配上。用线段树维护一下。

Code $O(n \log n)$

#include < algorithm >#include < cstdio >#define gec getchar#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__);typedef long long ll;templateinline void read(T&x){	x=0;bool f=0;char c=gec();	for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘);	for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘;	x=f?-x:x;}const int MAXN(300010);int n,m,h,Ans; int a[MAXN],b[MAXN];struct AXLE{	int a[MAXN],up;	void ins(int x){a[++up]=x;}	void build()	{		std::sort(a+1,a+1+up);		int _up=1;		for(int i=2;i<=up;i++)if(a[i]!=a[i-1])a[++_up]=a[i];		up=_up;	}	int Find(int x)	{		int l=1,r=up,mid,Ans=1;		for(;l<=r;)if(a[mid=(l+r)>>1]<=x)l=mid+1,Ans=mid;else r=mid-1;		return Ans;	}}axle;int min(int a,int b){return a>b?b:a;}struct SMT{	int nx[MAXN<<1][2],Sum[MAXN<<1],Mn[MAXN<<1],sl[MAXN<<1],sr[MAXN<<1],root,stot;	void update(int k)	{		Sum[k]=Sum[nx[k][0]]+Sum[nx[k][1]];		Mn[k]=min(Mn[nx[k][0]],Sum[nx[k][0]]+Mn[nx[k][1]]);	}		void build(int &k,int l,int r)	{		k=++stot; sl[k]=l; sr[k]=r; 		if(l==r){return ;}int mid=(l+r)>>1;		build(nx[k][0],l,mid);		build(nx[k][1],mid+1,r);			}		void modfiy(int k,int x,int y)	{		if(sl[k]==sr[k]){Sum[k]+=y;Mn[k]=Sum[k];return;}		int mid=(sl[k]+sr[k])>>1;		modfiy(nx[k][x>mid],x,y);		update(k);	}}tree;int main(){#ifndef ONLINE_JUDGE	FILE("C");#endif			read(n);read(m);read(h);	for(int i=1;i<=m;i++)read(b[i]),b[i]=h-b[i];	for(int i=1;i<=n;i++)read(a[i]);	for(int i=1;i<=n;i++)axle.ins(a[i]);	for(int i=1;i<=m;i++)axle.ins(b[i]);		axle.build();		for(int i=1;i<=m;i++)b[i]=axle.Find(b[i]);	for(int i=1;i<=n;i++)a[i]=axle.Find(a[i]);	tree.build(tree.root,1,axle.up);	for(int i=1;i<=m;i++)tree.modfiy(tree.root,b[i],1);	for(int l=1,r=0;r<n;)	{		while(r-l+1<m&&r<=n)tree.modfiy(tree.root,a[++r],-1);		if(tree.Mn[tree.root]>=0)Ans++;		while(r-l+1==m)tree.modfiy(tree.root,a[l++],1);	}	printf("%d\n",Ans);	return 0;}

LYOI#310. 「2017 山东一轮集训 Day3」第二题

 对于一棵有根树，定义一个点 u 的k-子树为 u 的子树中距离 u 不超过 k 的部分。注意，假如 u 的子树中不存在距离 u 为 k 的点，则 u 的 k-子树是不存在的。
定义两棵子树是相同的，当且仅当不考虑点的标号时，他们的形态是相同的（儿子的顺序也需要考虑）。
给定一棵 n 个点，点的标号在 [1,n]，以 1 为根的有根树。问最大的 k ，使得存在两个点 u≠v，满足 u 的 k−子树与 v 的 k−子树相同。$n \le 10^5$

想法：看到这个「儿子的顺序也需要考虑」，所以一个树可以用括号序列表示，括号序列也可以看出01串。01串比较就可以Hash了。于是解决判断子树形态。

然后可以用显然法证明k是单调的，二分答案后。对于一个节点x，其第k+1祖先的括号序列，就要去掉x的子树这一段区间。用Vector存下每个点被去掉的区间（显然不会相交），回溯时，依次合并没有去掉的区间的Hash值。每个点最多贡献一个区间，所以总O(n)

Code $O(n \log n)$

#include < map >#include < vector >#include < cstdio >#define gec getchar#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__);typedef long long ll;typedef unsigned long long ull;template < class T > inline void umax(T &a,T b){if(a<b)a=b;}template < class T >inline void read(T&x){	x=0;bool f=0;char c=gec();	for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘);	for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘;	x=f?-x:x;}const int MAXN(100010),Base(17271);int n,c,x,Ans;struct Node{	int nd,nx;}bot[MAXN];int tot,first[MAXN];void add(int a,int b){bot[++tot]=(Node){b,first[a]};first[a]=tot;}int inEu[MAXN],ouEu[MAXN],cnt,num[MAXN<<1],Dep[MAXN];void Dfs(int x){	inEu[x]=++cnt; num[cnt]=1; Dep[x]=1;	for(int v=first[x];v;v=bot[v].nx) Dfs(bot[v].nd),umax(Dep[x],Dep[bot[v].nd]+1);	ouEu[x]=++cnt;}ull H[MAXN<<1],Hash[MAXN<<1];void Get_Hash(){	H[0]=1;Hash[0]=0;	for(int i=1;i<=cnt;i++)	 H[i]=H[i-1]*Base,	 Hash[i]=Hash[i-1]*Base+num[i];}bool bf;int st[MAXN],tp;struct Data{int l,r;};std::vectorSeg[MAXN];std::map<ull,int>Map;int tm;ull Get(int l,int r){	ull Tmp=Hash[r];	Tmp-=Hash[l-1]*H[r-l+1];	return Tmp;}void Dfs2(int x,int k){	st[++tp]=x; 	if(tp>=k+1)	{		int fff=st[tp-k];		Seg[fff].push_back((Data){inEu[x],ouEu[x]});	}			for(int v=first[x];v;v=bot[v].nx)	{			Dfs2(bot[v].nd,k);	if(bf)return;	}	if(Dep[x]>=k)	{		ull val=0;int last=inEu[x];		for(int v=0,sz=Seg[x].size();v<sz;v++)		{			if(last<Seg[x][v].l)				val=val*H[ Seg[x][v].l-last ]+ Get(last,Seg[x][v].l-1);			last=Seg[x][v].r+1;		}		if(last<=ouEu[x]) val=val*H[ ouEu[x]-last+1 ]+Get(last,ouEu[x]);		if(Map[val]==tm)bf=1;		Map[val]=tm;	}	tp--;}bool Check(int k){	tp=0; tm++; bf=0; Dfs2(1,k); 	for(int i=1;i<=n;i++)Seg[i].clear();	return bf;}int main(){#ifndef ONLINE_JUDGE	FILE("C");#endif	read(n);	for(int i=1;i<=n;i++)	{		read(c);		while(c--) read(x),add(i,x);	}	Dfs(1); Get_Hash();	Ans=1;	for(int l=1,r=Dep[1],mid;l<=r;)	if(Check(mid=(l+r)>>1))l=mid+1,Ans=mid;else r=mid-1;	printf("%d\n",Ans-1);	return 0;}

一些题目