六校联考2019CSP 选做

更新中...

以下所有标注“片段”的参考代码，都缺少一个“头”，“头”里包括了一些我的习惯性的简写（如typedef long long ll;）。没有“头”并不影响理解代码。如果想要完整代码，可以去本博客公告栏的链接里，把这个“头”复制到“代码片段”前面。

day1-流量

题目链接

根据“每个点处流入的流量之和等于流出的流量之和”，当且仅当一个点仅有一条未知流量的边时，可以推断得知这条边的状态。当然，这种推断是会产生连锁反应的。例如，初始时，只有几个点满足“仅有一条未知流量的边”，然后我们把这些边推断出来后，又会产生一些新的点满足这一条件。

进一步，发现，如果还未确定状态的边（构成的子图）中存在一个环，则环上的边的流量，永远无法被推断出来。同时发现，若不存在环，则一定可以推断出所有边的流量（按上一段描述的过程，从叶子到根进行“连锁反应”即可）。因此，我们不询问的边的集合，就是原图的最大生成森林。

求这个最大生成森林即可。注意，(w_ileq 0)的边一定要询问（因为问了没有坏处），也就是不被加入最大生成森林中。最后，设最大生成森林的边权和为(s)，则答案就是((sum_{i=1}^{m}w_i)-s)。

时间复杂度(O(mlog m+nlog n))。

参考代码（片段）：

const int MAXN=2e5,MAXM=5e5;
int n,m,fa[MAXN+5],sz[MAXN+5];
int get_fa(int x){return (x==fa[x])?x:(fa[x]=get_fa(fa[x]));}
struct ed{int u,v,w;}e[MAXM+5];
bool cmp(ed x,ed y){return x.w>y.w;}
int main() {
	cin>>n>>m;ll sum=0;
	for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
	for(int i=1;i<=m;++i){cin>>e[i].u>>e[i].v>>e[i].w;sum+=e[i].w;}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;++i){
		if(e[i].w<=0)break;
		int u=get_fa(e[i].u),v=get_fa(e[i].v);
		if(u!=v){
			sum-=e[i].w;
			if(sz[u]>sz[v])swap(u,v);
			fa[u]=v;
			sz[v]+=sz[u];
		}
	}
	cout<<sum<<endl;
	return 0;
}

day1-个人练习生

题目链接

考虑二分答案( ext{mid})。可以对每个点(u)，求出一个( ext{lim}[u])表示点(u)最迟什么时候必须出发。

先令( ext{lim}[u]= ext{mid}-a[u]- ext{dep}[u])（( ext{dep}[u])是点(u)到根路径上的边数）。但这还不完全，因为我们还要考虑到“祖先必须在后代之后出发”这一要求。于是再做一遍dfs，让每个点的( ext{lim}[u])，对( ext{lim}[fa(u)]-1)取(min)。这样就求出了真正的( ext{lim}[u])：每个点的最迟出发时间。

然后可以做一个贪心：对( ext{lim}[1dots n])排序，让值小的先出发。发现当前答案( ext{mid})合法，当且仅当排好序后，(forall iin[1,n]: ext{lim}[i]geq i-1)。

因为要二分答案和排序，时间复杂度(O(ncdot log ncdot log a))，只能拿到(80)分。

发现其实不用二分答案。因为( ext{mid})的大小，并不会影响( ext{lim}[i])的相对大小关系。所以可以先假设( ext{mid}=0)，求出( ext{lim}[1dots n])并排好序。然后答案就等于：(max_{i=1}^{n}{i-1- ext{lim}[i]})。

时间复杂度(O(nlog n))，(log)来自排序。

参考代码（片段）：

const int MAXN=3e5,MAXA=1e9;
int n,a[MAXN+5];
vector<int>G[MAXN+5];
int fa[MAXN+5],dep[MAXN+5];
void dfs_prep(int u){
	for(int i=0;i<SZ(G[u]);++i){
		int v=G[u][i];
		if(v==fa[u]) continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs_prep(v);
	}
}
int lim[MAXN+5];
void dfs_calc_lim(int u){
	for(int i=0;i<SZ(G[u]);++i){
		int v=G[u][i];
		if(v==fa[u]) continue;
		lim[v]=min(lim[v],lim[u]-1);
		dfs_calc_lim(v);
	}
}
int main() {
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	for(int i=1;i<n;++i){
		int u,v; cin>>u>>v;
		G[u].pb(v); G[v].pb(u);
	}
	dfs_prep(1);
	for(int i=1;i<=n;++i)
		lim[i]=-a[i]-dep[i];
	dfs_calc_lim(1);
	sort(lim+1,lim+n+1);
	int ans=0;
	for(int i=1;i<=n;++i){
		ans=max(ans,i-1-lim[i]);
	}
	cout<<ans<<endl;
	return 0;
}

day1-假摔

题目链接

考虑一对可能成为最优方案的((A,B))，要满足什么条件。

如果存在一个(x)，满足(A<x<B)，且(a_xgeq a_A)，则((x,B,C))是一组更优的合法解。因此：(forall xin(A,B):a_x<a_A)。
如果存在一个(x)，满足(A<x<B)，且(a_xgeq a_B)，则((A,x,C))是一组更优的合法解，因此：(forall xin (A,B):a_x<a_B)。

因此，合法的((A,B))，总共只有(O(n))对：也就是每个位置(A)和它后面第一个(a_Bgeq a_A)的(B)；以及每个位置(B)，和它前面第一个(a_Ageq a_B)的(A)。可以用单调栈求出。

然后考虑回答询问。

离线。从大到小枚举左端点，每次加入一个(A)（也就是加入若干对((A,B))）。

对每个位置(i)，假设我们维护出一个(f[i])表示以(i)作为(C)时的最优答案。假设当前枚举到的左端点为(l)，当前要处理的询问右端点为(r)，则我们只需要查询(f)数组在([l,r])区间内的最大值即可。

考虑加入一个(A)对(f)数组的影响。前面说过，这也就是加入以它为(A)的所有((A,B))。因为((A,B))总数只有(O(n))对，所以可以暴力依次加入。对一对((A,B))而言，它影响到的(C)，必须满足(B-Aleq C-B)，移项得(Cgeq 2B-A)。因此我们对所有(igeq 2B-A)，令(f[i])对(a_A+a_B+a_i)取(max)即可。

用线段树维护。修改操作有些特殊。做法是，预处理出每个区间，初始时(a_i)的最大值，记为( ext{maxa}(l,r))。这样区间修改时，令( ext{maxf}(l,r):=max( ext{maxf}(l,r), ext{maxa}(l,r)+a_A+a_B))即可。区间查询就是直接求( ext{maxf})的最大值。

时间复杂度(O((n+q)log n))。

考虑这道题的本质。一开始是一个((A,B,C))三元问题，很不好回答。我们是怎么拆解它的？用离线去掉了一元(A)，通过观察(A,B)的关系去掉了一元(B)，然后剩下的一元(C)用数据结构维护它。

参考代码（片段）：

const int MAXN=5e5;
pii sta[MAXN+5];
int n,m,a[MAXN+5],top;
ll ans[MAXN+5];
struct Q{int l,r,id;}q[MAXN+5];
bool cmp(Q x,Q y){return x.l>y.l;}
struct SegmentTree{
	//区间取max,求区间max
	ll val[MAXN*4+5],tag[MAXN*4+5],mx[MAXN*4+5];
	void build(int p,int l,int r){
		if(l==r){val[p]=mx[p]=a[l];return;}
		int mid=(l+r)>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		val[p]=mx[p]=max(val[p<<1],val[p<<1|1]);
	}
	void push_down(int p){
		if(tag[p]){
			val[p<<1]=max(val[p<<1],mx[p<<1]+tag[p]);
			val[p<<1|1]=max(val[p<<1|1],mx[p<<1|1]+tag[p]);
			tag[p<<1]=max(tag[p<<1],tag[p]);
			tag[p<<1|1]=max(tag[p<<1|1],tag[p]);
			tag[p]=0;
		}
	}
	void modify(int p,int l,int r,int ql,int qr,ll v){
		if(ql<=l && qr>=r){val[p]=max(val[p],mx[p]+v);tag[p]=max(tag[p],v);return;}
		push_down(p);
		int mid=(l+r)>>1;
		if(ql<=mid)modify(p<<1,l,mid,ql,qr,v);
		if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,v);
		val[p]=max(val[p<<1],val[p<<1|1]);
	}
	ll query(int p,int l,int r,int ql,int qr){
		if(ql<=l && qr>=r)return val[p];
		push_down(p);
		int mid=(l+r)>>1;ll res=0;
		if(ql<=mid)res=query(p<<1,l,mid,ql,qr);
		if(qr>mid)res=max(res,query(p<<1|1,mid+1,r,ql,qr));
		return res;
	}
}T;
int main() {
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;++i){cin>>q[i].l>>q[i].r;q[i].id=i;}
	sort(q+1,q+m+1,cmp);
	T.build(1,1,n);
	sta[top=1]=mk(a[n-1],n-1);
	int j=n-2;
	for(int i=1;i<=m;){
		for(;j>=q[i].l;--j){
			while(top && sta[top].fst<=a[j]){
				if(sta[top].scd*2-j<=n)T.modify(1,1,n,sta[top].scd*2-j,n,a[j]+sta[top].fst);
				--top;
			}
			if(top&&sta[top].scd*2-j<=n)T.modify(1,1,n,sta[top].scd*2-j,n,a[j]+sta[top].fst);
			sta[++top]=mk(a[j],j);
		}
		int ii=i;
		for(;ii<=m&&q[ii].l==q[i].l;++ii)ans[q[ii].id]=T.query(1,1,n,q[ii].l+2,q[ii].r);
		i=ii;
	}
	for(int i=1;i<=m;++i)cout<<ans[i]<<endl;
	return 0;
}

day2-文体两开花

题目链接

对每个点，维护一个(f(u))表示它所有儿子的(val)的异或和。再维护一个(g(u))，表示所有儿子的(f)的异或和。

这样，修改和查询都可以(O(1))维护。

时间复杂度(O(n+q))。

参考代码（片段）：

const int MAXN=1e6,MOD=1e9+7;
int n,m,val[MAXN+5],fa[MAXN+5],f[MAXN+5],g[MAXN+5];
vector<int>G[MAXN+5];
void dfs(int u){
	f[u]=val[u];
	for(int i=0;i<(int)G[u].size();++i){
		int v=G[u][i];
		if(v==fa[u])continue;
		fa[v]=u;
		dfs(v);
		f[u]^=val[v];
		g[u]^=f[v];
	}
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;++i)cin>>val[i];
	for(int i=1,u,v;i<n;++i){cin>>u>>v;G[u].pb(v),G[v].pb(u);}
	dfs(1);f[0]=val[1];
	int ans=0;
	for(int i=1;i<=m;++i){
		int u,x;cin>>u>>v;
		if(fa[fa[u]])g[fa[fa[u]]]^=f[fa[u]];
		g[fa[u]]^=val[u];g[fa[u]]^=x;
		f[fa[u]]^=val[u];f[fa[u]]^=x;
		f[u]^=val[u];f[u]^=x;
		if(fa[fa[u]])g[fa[fa[u]]]^=f[fa[u]];
		ans=(ans+(ll)(g[u]^f[fa[u]]^val[fa[fa[u]]])%MOD*i%MOD*i%MOD)%MOD;
		val[u]=x;
	}
	cout<<ans<<endl;
	return 0;
}

day2-国际影星

题目链接

补集转化，求不合法的方案，也就是点(1)能到达的点与点(2)能到达的点交为空。

因为(n)很小。考虑状压DP。设(dp_{1/2}[S])，表示从点(1)或(2)出发，只考虑点集(S)及其内部的边的情况下，能到达(S)里任意一个点，此时给点集(S)内部的边定向的方案数。

更明确地讲，一个点集内部的边，就是指两个端点都在点集里的边。我们不难对每个点集，预处理出它内部的边的数量，记为(E[S])。

转移时，还是考虑补集转化，用总的方案减去不合法的方案。总的方案就是(2^{E[S]})，即任意连边。考虑计算不合法的方案数。枚举一个真子集(Tsubsetneq S)，计算恰好只能到达点集(T)的方案数（显然(1)或(2)必须在(T)中）。此时(Ssetminus T)内部可以任意连边，而(T)与(Ssetminus T)之间的边必须都连向(T)。所以可以得到转移：

[dp_{x}[S]=2^{E[S]}-sum_{Tsubsetneq S,xin T}dp_{x}[T] imes 2^{E[Ssetminus T]} ]

DP完成后，考虑统计答案。枚举两个互不相交的集合(s_1,s_2)表示最终(1)能到达的点集和(2)能到达的点集。设(r)表示其他点的集合，即(r={1,dots ,n}setminus s_1setminus s_2)。则(r)内部的的边可以任意连，而(r)与(s_1,s_2)之间的边必须全部连向(s_1)或(s_2)。(s_1,s_2)之间不能有连边。

[ ext{ans}=2^{m}-sum_{substack{s1,s2in{1,dots,n}\s_1cap s_2=emptyset\ ext{EdgeBetween}(s_1,s_2)=emptyset\1in s_1,2in s_2}}dp_1[s_1] imes dp_2[s_2] imes 2^{E[r]} ]

主要涉及到子集枚举，用这个技巧：for(int i=s; i; i=((i-1)&s)) 可以实现不重不漏的枚举。

时间复杂度(O(3^n))。

参考代码（片段）：

const int M=(1<<16),MOD=1e9+7;
inline int mod(int x){return x<MOD?(x<0?x+MOD:x):x-MOD;}
int n,m,G[16],pw[300],cnt[M],f[M],g[M];
int main() {
	pw[0]=1;for(int i=1;i<300;++i)pw[i]=mod(pw[i-1]<<1);
	n=read();m=read();
	for(int i=1;i<=m;++i){int u=read()-1,v=read()-1;G[u]|=(1<<v);G[v]|=(1<<u);}
	for(int s=1;s<(1<<n);++s){
		for(int i=0;i<n;++i)if(s&(1<<i))cnt[s]+=__builtin_popcount(G[i]&s);
		cnt[s]>>=1;
	}
	f[1]=1;
	for(int s=5;s<(1<<n);s+=4){
		f[s]=pw[cnt[s]];
		int c=s^1;
		for(int ss=(c-1)&s;;ss=(ss-1)&s){
			f[s]=mod(f[s]-(ll)f[ss^1]*pw[cnt[c^ss]]%MOD);
			if(!ss)break;
		}
	}
	g[2]=1;
	for(int s=6;s<(1<<n);s+=4){
		g[s]=pw[cnt[s]];
		int c=s^2;
		for(int ss=(c-1)&s;;ss=(ss-1)&s){
			g[s]=mod(g[s]-(ll)g[ss^2]*pw[cnt[c^ss]]%MOD);
			if(!ss)break;
		}
	}
	int ans=pw[m];
	for(int s1=1;s1<(1<<n);s1+=4){
		int c=s1;
		for(int i=0;i<n;++i)if(s1&(1<<i))c|=G[i];
		if(c&2)continue;
		c=(((1<<n)-1)&(~c))^2;
		for(int s2=c;;s2=(s2-1)&c){
			ans=mod(ans-(ll)f[s1]*g[s2^2]%MOD*pw[cnt[((1<<n)-1)^s1^(s2^2)]]%MOD);
			if(!s2)break;
		}
	}
	cout<<ans<<endl;
	return 0;
}

day2-零糖麦片

题目链接

相当于有一个(01)序列，每次可以让连续的一段异或(1)。初始时有(k)个位置上是(1)。问最少多少次操作后，可以把整个序列变成(0)。

对原序列做(operatorname{xor})意义下的差分。具体来说，设原序列为(a[0dots n])，并且钦定(a[0]=0)。那么差分序列就是(b[1dots n])满足(b[i]=a[i]operatorname{xor}a[i-1])。

那么“让一段区间异或(1)”，就变成了让差分序列上两个点异或(1)。并且原序列全是(0)，就等价于差分序列全是(0)（充分必要）。

要把差分序列上这些(1)消去，考虑将它们两两匹配。对于一对匹配了的(1)，要将它们消去：

如果他们距离为一个奇质数，则需要(1)次操作。
如果他们距离为一个偶数，则需要(2)次操作。这是根据哥德巴赫猜想：任何一个大于等于(6)的偶数一定能拆成两个奇质数的和，并且它被证明在(10^7)以内是正确的。
如果他们距离为一个非质数的奇数，则需要(3)次操作：拆成一个奇质数和一个偶数。

于是根据贪心，我们肯定希望距离为奇质数的匹配尽可能多。又发现这样的匹配，两个点一定一个是奇数一个是偶数，所以可以根据奇偶性建二分图，求出最大匹配。

剩下的点，尽量和同奇偶性的匹配即可。

时间复杂度(O( ext{flow}(k,k^2)))。

const int N=1e7,INF=1e9;
int n,a[1005],p[1000000],cntp,pos0[2005],pos1[2005],ct0,ct1;
bool v[N+1];
void sieve(){
	v[1]=1;
	for(int i=2;i<=N;++i){
		if(!v[i])p[++cntp]=i;
		for(int j=1;j<=cntp&&i*p[j]<=N;++j){
			v[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
}
namespace Flowinginging{
	const int MAXN=2010;
	struct EDGE{int nxt,to,w;}edge[MAXN*MAXN];
	int head[MAXN],tot;
	void add_edge(int u,int v,int w){
		edge[++tot].nxt=head[u];edge[tot].to=v;edge[tot].w=w;head[u]=tot;
		edge[++tot].nxt=head[v];edge[tot].to=u;edge[tot].w=0;head[v]=tot;
	}
	int d[MAXN],cur[MAXN];
	bool bfs(int s,int t){
		memset(d,0,sizeof(d));d[s]=1;
		queue<int>q;q.push(s);
		while(!q.empty()){
			int u=q.front();q.pop();
			for(int i=head[u];i;i=edge[i].nxt){
				int v=edge[i].to;
				if(!d[v]&&edge[i].w){
					d[v]=d[u]+1;
					if(v==t)return 1;
					q.push(v);
				}
			}
		}
		return 0;
	}
	int dfs(int u,int t,int flow){
		if(u==t)return flow;
		int rest=flow;
		for(int &i=cur[u];i&&rest;i=edge[i].nxt){
			int v=edge[i].to;
			if(d[v]==d[u]+1 && edge[i].w){
				int k=dfs(v,t,min(rest,edge[i].w));
				if(!k)d[v]=0;
				else{
					edge[i].w-=k;
					edge[i^1].w+=k;
					rest-=k;
					//return flow-rest;
				}
			}
		}
		return flow-rest;
	}
	int maxflow(int s,int t){
		int ans=0,tmp;
		while(bfs(s,t)){
			for(int i=1;i<=t;++i)cur[i]=head[i];
			while(tmp=dfs(s,t,INF))ans+=tmp;
		}
		return ans;
	}
};
using namespace Flowinginging;
int main() {
	sieve();
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;){
		int j=i+1;
		while(j<=n && a[j]==a[j-1]+1)++j;
		--j;
		if(a[i]&1)pos1[++ct1]=a[i];else pos0[++ct0]=a[i];
		if((a[j]+1)&1)pos1[++ct1]=a[j]+1;else pos0[++ct0]=a[j]+1;
		i=j+1;
	}
	sort(pos0+1,pos0+ct0+1);
	sort(pos1+1,pos1+ct1+1);
	int s=ct0+ct1+1,t=s+1;
	tot=1;
	for(int i=1;i<=ct0;++i){
		add_edge(s,i,1);
		for(int j=1;j<=ct1;++j){
			int d=abs(pos1[j]-pos0[i]);assert(d<=N);
			if(!v[d])add_edge(i,ct0+j,1);
		}
	}
	for(int i=1;i<=ct1;++i)add_edge(ct0+i,t,1);
	int ans=maxflow(s,t);
	ct0-=ans;ct1-=ans;
	ans+=(ct0/2)*2+(ct1/2)*2;
	if(ct0&1)ans+=3;
	cout<<ans<<endl;
	return 0;
}

day3-序列

题目链接

考虑要使原序列前(i)个位置的和是(m)的倍数。发现，不管前(i-1)个位置怎么填，第(i)个位置都有且仅有唯一一种填法，使得和是(m)的倍数。同理，也会有恰好(m-1)种填法，使得和不是(m)的倍数。

于是问题就转化为，钦定(j) ((jgeq k))个位置前缀和是(m)的倍数，其他位置都不是。因此答案等于：

[sum_{j=k}^{n}{nchoose j}(m-1)^{n-j} ]

预处理阶乘和逆元，可以(O(1))求组合数。总时间复杂度(O(n))。

参考代码（片段）：

const int MAXN=1e5,MOD=998244353;
inline int mod(int x){return x<MOD?x:x-MOD;}
inline int pow_mod(int x,int i){
	int y=1;
	while(i){
		if(i&1)y=(ll)y*x%MOD;
		x=(ll)x*x%MOD;
		i>>=1;
	}
	return y;
}
int n,m,K,fac[MAXN+5],invf[MAXN+5];
inline int comb(int n,int k){
	if(n<k)return 0;
	return (ll)fac[n]*invf[k]%MOD*invf[n-k]%MOD;
}
int main() {
	fac[0]=1;for(int i=1;i<=MAXN;++i)fac[i]=(ll)fac[i-1]*i%MOD;
	invf[MAXN]=pow_mod(fac[MAXN],MOD-2);
	for(int i=MAXN-1;i>=0;--i)invf[i]=(ll)invf[i+1]*(i+1)%MOD;
	int T;cin>>T;while(T--){
		cin>>n>>m>>K;
		if(K>n){puts("0");continue;}
		int t=pow_mod(m-1,n-K),iv=pow_mod(m-1,MOD-2),ans=0;
		for(int i=K;i<=n;++i){
			ans=mod(ans+(ll)comb(n,i)*t%MOD);
			t=(ll)t*iv%MOD;
		}
		cout<<ans<<endl;
	}
	return 0;
}

day3-图

题目链接

考虑给图上的点染色，使得在最终的答案路径中，(k)个点的颜色都各不相同。这样我们就可以状压DP解决。设(dp[s][u])表示已经经过了(s)里的这些颜色，走到了点(u)，经过的最长路径长度。转移时枚举下一步走到哪里。时间复杂度(O(2^k(n+m)))。

现在问题是我们还不知道这个染色方案。考虑随机染色：每个点的颜色在(k)种颜色里随机。

这样总共有(k^n)种染色方案。其中能使得答案路径上点颜色各不相同的染色方案有(k!cdot k^{n-k})。正确率是(frac{k!cdot k^{n-k}}{k^n}=frac{k!}{k^k})。

多次随机，可以通过本题。

参考代码（片段）：

const int MAXN=3e4;
struct EDGE{int nxt,to,w;}edge[200005];
int n,m,K,head[MAXN+5],tot,ans,f[MAXN+5][1<<8],col[MAXN+5],M;
inline void add_edge(int u,int v,int w){edge[++tot].nxt=head[u];edge[tot].to=v;edge[tot].w=w;head[u]=tot;}
void solve(){
	for(int i=1;i<=n;++i){
		col[i]=rand()%K;
		for(int j=0;j<M;++j)f[i][j]=-1;
		f[i][1<<col[i]]=0;
	}
	for(int s=1;s<M-1;++s){
		for(int u=1;u<=n;++u){
			if(f[u][s]<0)continue;
			for(int i=head[u];i;i=edge[i].nxt){
				int v=edge[i].to;
				if(!(s&(1<<col[v])) && f[v][s^(1<<col[v])]<f[u][s]+edge[i].w){
					f[v][s^(1<<col[v])]=f[u][s]+edge[i].w;
				}
			}
		}
	}
	for(int i=1;i<=n;++i)ans=max(ans,f[i][M-1]);
}
int main() {
	srand((ull)"dysyn1314");
	cin>>n>>m>>K;
	for(int i=1,u,v,w;i<=m;++i){cin>>u>>v>>w;add_edge(u,v,w);add_edge(v,u,w);}
	int beg=clock();M=1<<K;ans=-1;
	while(1.0*(clock()-beg)/CLOCKS_PER_SEC<1.5)solve();
	cout<<ans<<endl;
	return 0;
}

day3-商店

题目链接

简化一下问题。有三个序列(a[1dots n],b[1dots n],c[1dots n])。满足 (forall i: a[i]geq b[i])。你要选出一个({1,dots,n})的子集(S)。满足：

[left(sum_{iin S}a[i] ight)geq p\ left(sum_{iin S}b[i] ight)leq p ]

并且最大化：

[sum_{iin S} c[i] ]

朴素的DP：设(dp[i][x][y])表示考虑了前(i)个物品，选出的物品(a)之和为(x)，(b)之和为(y)，能得到的最大的(c)之和。转移时考虑当前物品选或不选，是(O(1))的。总时间复杂度(O(np^2))。

发现这个DP没有用到一个重要的条件：(forall i:a[i]geq b[i])。

考虑这样一个状态：(dp[i][z])，表示考虑了前(i)个物品，选出的物品(a)之和(geq z)，(b)之和(leq z)。发现每个(z-a[i]leq z'leq z-b[i])，都可以转移到(z)。也就是说，对每个(i)，我们枚举(z)之后，能转移到每个(z)的是一段长度相同的滑动窗口。用单调队列维护这段滑动窗口里(dp[i-1][z'])的最大值即可。

时间复杂度(O(np))。空间可以用滚动数组优化到(O(n+p))。

参考代码（片段）：

int n,p,a[1005],b[1005],c[1005];
ll dp[2][100005];
int main() {
	cin>>n>>p;
	for(int i=1;i<=n;++i)cin>>a[i];
	for(int i=1;i<=n;++i)cin>>b[i];
	for(int i=1;i<=n;++i)cin>>c[i];
	memset(dp,0x3f,sizeof(dp));dp[0][0]=0;
	for(int i=1,ti=1;i<=n;++i,ti^=1){
		deque<int>dq;
		for(int j=0;j<=p;++j){
			while(!dq.empty()&&dq.front()<j-a[i])dq.pop_front();
			if(j-b[i]>=0){
				while(!dq.empty()&&dp[ti^1][dq.back()]>=dp[ti^1][j-b[i]])dq.pop_back();
				dq.push_back(j-b[i]);
			}
			dp[ti][j]=dp[ti^1][j];
			if(!dq.empty())dp[ti][j]=min(dp[ti][j],dp[ti^1][dq.front()]+c[i]);
		}
	}
	cout<<dp[n&1][p]<<endl;
	return 0;
}

day9-谦逊

题目链接

引理1：任何一个数经过若干次谦逊操作，一定能得到一个小于等于(9)的数。并且，假设原数是(x)，则得到的这个“小于等于(9)的数”就是((x-1)mod 9+1)。也就是说，对于$x=1,2,dots $，最终得到的结果，每(9)个数为一周期，不断循环。

引理2：(forall k)，(i imes kmod 9)的值，对所有(i=0,1,2,dots)，每(9)个数为一周期，永远循环。

引理3：任何一个小于(10^{16})的数，最多需要用(3)次谦逊操作，就能变成小于等于(9)的数。

以上三条引理都可以通过简单的找规律或逻辑分析得出。此处略去证明。

根据引理1可知，任何数使用谦逊的结果，只和它模(9)的余数有关。又根据引理2，对于一个(k)，想要得到所有可能的模(9)余数，只需要使用不超过(8)次力量祝福。综上，我们最多使用(8)力量祝福，一定能得到最优答案。

容易想到的一种做法是，枚举使用力量祝福的次数(i) ((0leq ileq 8))，用(( ext{digitSum}(n+i imes k),i+ ext{calc}(n+i imes k)))更新答案。其中( ext{digitSum})表示数位和，( ext{calc})表示变成小于等于(9)的数，需要使用的谦逊操作数。

但上述的做法是不对的。虽然能求出最优的结果，却不一定能最小化操作次数。也就是说，有可能在中间某一步先搞一次谦逊操作，会比使用完所有力量祝福后再一起用谦逊更优。

那怎么办呢？如果你转而去想高妙的贪心，或挖掘更深的性质，就容易陷入自闭。此时需要用到引理3，也就是( ext{calc}(n+i imes k))的值不超过(3)。所以总操作次数最多为(11)。我们可以爆搜所有可能的操作方案！按最坏情况粗略估计，大约要搜(sum_{x=1}^{11}2^x< 2^{12})种操作方案，实际远远达不到。可以轻松AC本题。

时间复杂度(O(?))。

参考代码（片段）：

ll sum_dig(ll x){
	ll res=0;
	while(x)res+=(x%10),x/=10;
	return res;
}
ll N,K;
pii ans;
void dfs(int u,int v,ll n){
	if(n<=9)
		ckmin(ans, mk((int)n,u+v));
	if(u+v==11)
		return;
	if(u<8){
		dfs(u+1,v,n+K);
	}
	if(v<3){
		dfs(u,v+1,sum_dig(n));
	}
}
void solve_case(){
	cin>>N>>K;
	ans=mk(10,233);
	dfs(0,0,N);
	cout<<ans.fi<<" "<<ans.se<<endl;
}
int main() {
	int T;cin>>T;while(T--){
		solve_case();
	}
	return 0;
}

day9-排序

题目链接

官方题解给出的构造方案（原文）：

首先给每个格子钦点一个可接受的范围区间。
然后依次一个一个处理左上角格子的数，把它移到应该去的格子里。如上图，如果左上角最上层的盘子是(83)，我们就把它移到((1,3))去，然后处理下一个。
然后按从大区间到小区间的次序把所有区间移到右下角，使它们最后是排好序的。如上图，先把([91−99])移到右下角，然后是([81−90])，以此类推。

也就是说，我们把左上角(6 imes6)的问题，转化成若干个小子问题。从大到小，依次递归解决每个子问题，最终就能把整个局面排好序了。

那我们现在就要问：一个(n imes m)的矩阵，从左上角进、右下角出，最多能把多少个盘子排好序。我们可以严谨地说明一下，“进”就是指左上角的格子原本是空的，然后我们突然放一堆盘子进来，它们是乱序的；“出”就是指把这些盘子，按下面大、上面小的顺序排好后，堆叠到右下角的格子上方（右下角的格子里可能原本已有一些盘子，不过不影响。我们放在它们上面即可）。具体到本题中，其实所有的“右下角”，都是指整个(6 imes6)矩形的右下角，也就是坐标((6,6))的这个格子；而左上角，则不确定只哪个格子，取决于我们讨论的(n imes m)的大小。

我们记，一个(n imes m)的矩阵，最多能把多少个盘子排好序，这个数量为(f(n,m))。

首先，(f(1,1)=1)。

然后根据前面所说，我们解决这个问题的方法其实就是分治（把要排序的数分发下去）。所以除了左上角外的每个格子，都被分发到一段数。因此他们能排序的量的总和，就是(n imes m)能排序的数量。即：(f(n,m)=sum_{i=1}^{n}sum_{j=1}^{m}[(i,j) eq (n,m)] imes f(i,j))。

按此式子计算，得出(f(6,6)=26928)。不足以通过本题。

发现(1 imes 2)或(2 imes 1)的格子，通过手动构造，能排好(2)个盘子而非(1)个。所以强制令(f(1,2)=f(2,1)=2)后，可以算出(f(6,6)=42960)，可以通过本题。

时间复杂度(O(n))。

具体的递归实现，可以见代码。希望本题可以帮助读者更好的理解“分治”和“排序”这两个基础概念。

参考代码（片段）：

const int MAXN=4e4;
int f[10][10];
int n;
struct Oper{
	int r,c,num;
	char d;
	Oper(int _r,int _c,char _d,int _num){
		r=_r; c=_c; d=_d; num=_num;
	}
	Oper(){}
};
vector<Oper>ans;
void move(int frm_r,int frm_c,int to_r,int to_c){
	int r=frm_r, c=frm_c;
	while(r<to_r){
		ans.pb(Oper(r,c,'D',1));
		++r;
	}
	while(c<to_c){
		ans.pb(Oper(r,c,'R',1));
		++c;
	}
}
void solve(int pos_r,int pos_c,int val_l,int val_r,vector<int> a){
	if(!SZ(a)) return;
	if(pos_r==6 && pos_c==6) return;
	if(pos_r==5 && pos_c==6){
		assert(SZ(a)<=2);
		if(SZ(a)==1) move(5,6,6,6);
		else{
			if(a[0]>a[1]) ans.pb(Oper(5,6,'D',2));
			else{ move(5,6,6,6); move(5,6,6,6); }
		}
		return;
	}
	if(pos_r==6 && pos_c==5){
		assert(SZ(a)<=2);
		if(SZ(a)==1) move(6,5,6,6);
		else{
			if(a[0]>a[1]) ans.pb(Oper(6,5,'R',2));
			else{ move(6,5,6,6); move(6,5,6,6); }
		}
		return;
	}
	vector<vector<pii> > range(7,vector<pii>(7));
	vector<vector<vector<int> > > vec(7,vector<vector<int> >(7));
	int cur=val_l;
	for(int i=pos_r;i<=6;++i){
		for(int j=pos_c+(i==pos_r);j<=6;++j){
			int size=f[6-i+1][6-j+1];
			range[i][j]=mk(cur,cur+size-1);
			cur+=size;
		}
	}
	assert(cur-1>=val_r);
	for(int k=SZ(a)-1;k>=0;--k){
		int x=a[k];
		assert(val_l<=x && val_r>=x);
		bool flag=0;
		for(int i=pos_r;i<=6;++i){
			for(int j=pos_c+(i==pos_r);j<=6;++j){
				if(range[i][j].fi<=x && range[i][j].se>=x){
					vec[i][j].pb(x);
					move(pos_r,pos_c,i,j);
					flag=1;break;
				}
			}
			if(flag)break;
		}
		assert(flag);
	}
	for(int i=6;i>=pos_r;--i){
		for(int j=6;j>=pos_c+(i==pos_r);--j){
			solve(i,j,range[i][j].fi,range[i][j].se,vec[i][j]);
		}
	}
}
int main() {
	for(int i=1;i<=6;++i){
		for(int j=1;j<=6;++j){
			if(i==1 && j==1){
				f[i][j]=1;
				continue;
			}
			if((i==1 && j==2) || (i==2 && j==1)){
				f[i][j]=2;
				continue;
			}
			f[i][j]=0;
			int tmp=0;
			for(int x=1;x<=i;++x)for(int y=1;y<=j;++y){
				tmp+=f[x][y];
			}
			f[i][j]=tmp;
		}
	}
	cerr<<f[6][6]<<endl;
	
	cin>>n;
	vector<int>a;
	a.resize(n);
	for(int i=0;i<n;++i){
		cin>>a[i];
	}
	solve(1,1,1,n,a);
	cout<<SZ(ans)<<endl;
	for(int i=0;i<SZ(ans);++i){
		cout<<ans[i].r<<" "<<ans[i].c<<" "<<ans[i].d<<" "<<ans[i].num<<endl;
	}
	return 0;
}

day9-猜拳

再解决最后一点细节就来更新。

day10-数学题

题目链接

假设已经知道了(p,q,k)。我们可以用一个二元组，来描述(n=p^kq^k)的每个约数：二元组((a,b))表示(p^aq^b) ((0leq a,bleq k))。

考虑将所有这样的二元组，按(p^aq^b)排序。然后做一个DP。设(dp[i][x][y])表示考虑了前(i)个二元组，当前选出的二元组中，(p)的指数和为(x)，(q)的指数和为(y)，的方案数。由于同一个二元组可以选多次，我们可以按照完全背包的方法，把第一维去掉，然后每次从小到大枚举(x,y)。

答案就是(dp[k][k])。

我们发现，这个DP的结果，与(p,q)具体是多少无关。因为我们做的DP是一个背包，与物品的顺序没有关系。只要选出一个物品的集合，那一定能有唯一的一种方法将其排好序变成一个序列。

既然与(p,q)无关，那么可以对每个(k)，用上述的DP预处理它的答案。物品有(k^2)个，所以DP的时间复杂度是(O(k^4))的。因为(2^{24} imes3^{24}>10^{18})，所以(k)最大不超过(23)。枚举每个(k)做一遍这样的DP，复杂度是(23^5)。

然后处理每个询问，最关键的问题是要求出(k)。可以从(23)到(1)枚举所有可能的(k)，利用( exttt{C++})自带的( exttt{pow})函数对(n)开(k)次根（也就是( exttt{pow((long double)n,1.0/k)})），然后再检验这个开根结果（取整后）的(k)次方是否等于(n)。由于精度问题，取整最好把一定范围内上下几个数都试一遍。

设( exttt{pow})函数的时间复杂度是(P(n))，则总时间复杂度(O(23^5 + T imes 23 imes (P(n)+23)))。其中最后(P(n)+23)也可以变成(P(n)+log 23)，取决于检验开根结果时，是否使用快速幂。

参考代码（片段。需添加读入优化）：

// 请添加读入优化！！！

ll n;
ll ans[25],dp[25][25];
void init(){
	for(int K=1;K<=23;++K){
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(int i=0;i<=K;++i){
			for(int j=(i==0);j<=K-(i==K);++j){
				for(int x=0;x<=K-i;++x){
					for(int y=0;y<=K-j;++y){
						dp[x+i][y+j]+=dp[x][y];
					}
				}
			}
		}
		ans[K]=dp[K][K];
		cerr<<ans[K]<<endl;
	}
}
inline ll qpow(ll x,int i){
	ll y=1;
	while(i){
		if(i&1){
			y*=x;
		}
		x*=x;
		i>>=1;
	}
	return y;
}
void solve_case(){
	cin>>n;
	for(int i=23;i>=1;--i){
		ll pq = pow((long double)n,1.0/i);
		for(ll x=max(pq-1,1LL);x<=pq+1;++x){
			ll pw=qpow(x,i);
//			for(int j=1;j<=i;++j){
//				pw*=x;
//			}
			if(pw==n){
				cout<<ans[i]<<endl;
				return;
			}
		}
	}
	cerr<<n<<endl;
	assert(0);
}
int main() {
	init();
	int T;cin>>T;while(T--){
		solve_case();
	}
	return 0;
}

day10-城市

对于两个城市 (i,j)，如果 (a_ioperatorname{and}a_j eq 0)，题目说它们之间会有一条边权为 ( ext{lowbit}(a_i operatorname{and} a_j)) 的边。但其实，我们可以对所有 (a_ioperatorname{and}a_j) 里是 (1) 的二进制位，都连一条对应位权的边。显然这样不会改变答案。

于是问题转化为，对于一个点 (i)，检查它的每个为 (1) 的二进制位 (k) ((0leq k<32))。然后从 (i) 向所有二进制下第 (k) 位为 (1) 的点连一条边权为 (2^k) 的边。

既然是向某一类点集体连边，那么可以建虚点。也就是建 (32) 个点分别表示 (k=0dots 31)，然后从每个 (i) 向这些虚点连边，再从虚点向对应的 (j) 连边。这样总边数是 (O(nlog a)) 的。跑一个最短路，时间复杂度 (O(nlog alog n))。

代码略。

day10-好 ♂ 朋 ♂ 友

注意到，一个序列的前缀 (operatorname{or}) 和只会变化 (O(log a)) 次。因为每次的变化，相当于把一些位变成 (1)，而某一位一旦从 (0) 变成 (1)，就不会再改变了。

把询问离线。从大到小枚举询问的左端点。每次添加一个可能的，子段的左端点 (i)。考虑从 (i) 到 (n) 的这段序列，它的前缀 (operatorname{or}) 和总共会变化 (O(log a)) 次。这些变化的位置可以 (O(nlog a)) 预处理出来，做法是从后往前，递推求 ( ext{nxt}(i,j)) 表示位置 (i) 后面第一个第 (j) 位为 (1) 的数在哪。

枚举这 (O(log a)) 段东西，若数值合法，则考虑这一段对询问的贡献。用一个数组维护，以每个 (r) 为右端点的合法子段数量。则每次的贡献，相当于对这个数组做区间加。回答询问则相当于是区间求和。可以用线段树维护。

时间复杂度(O(m log n + nlog alog n))。

参考代码：

// problem: nflsoj475
#include <bits/stdc++.h>
using namespace std;

#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
	if (S == T) {
		T = (S = buf) + fread(buf, 1, SIZE, stdin);
		if (S == T) return '
';
	}
	return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
	fwrite(buf, 1, S - buf, stdout);
	S = buf;
}
inline void putchar(char c) {
	*S++ = c;
	if (S == T) flush();
}
struct NTR {
	~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
	#define getchar Fread :: getchar
	#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
	template<typename T>
	Reader& operator >> (T& x) {
		char c = getchar();
		T f = 1;
		while (c < '0' || c > '9') {
			if (c == '-') f = -1;
			c = getchar();
		}
		x = 0;
		while (c >= '0' && c <= '9') {
			x = x * 10 + (c - '0');
			c = getchar();
		}
		x *= f;
		return *this;
	}
	Reader& operator >> (char& c) {
		c = getchar();
		while (c == '
' || c == ' ') c = getchar();
		return *this;
	}
	Reader& operator >> (char* str) {
		int len = 0;
		char c = getchar();
		while (c == '
' || c == ' ') c = getchar();
		while (c != '
' && c != ' ') {
			str[len++] = c;
			c = getchar();
		}
		str[len] = '';
		return *this;
	}
	Reader(){}
} cin;
const char endl = '
';
struct Writer {
	template<typename T>
	Writer& operator << (T x) {
		if (x == 0) { putchar('0'); return *this; }
		if (x < 0) { putchar('-'); x = -x; }
		static int sta[45];
		int top = 0;
		while (x) { sta[++top] = x % 10; x /= 10; }
		while (top) { putchar(sta[top] + '0'); --top; }
		return *this;
	}
	Writer& operator << (char c) {
		putchar(c);
		return *this;
	}
	Writer& operator << (char* str) {
		int cur = 0;
		while (str[cur]) putchar(str[cur++]);
		return *this;
	}
	Writer& operator << (const char* str) {
		int cur = 0;
		while (str[cur]) putchar(str[cur++]);
		return *this;
	}
	Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end

const int MAXN = 1e5;
const int MAXM = 1e6;
const int LOGA = 29;

int n, m, K;
bool good[10];
int a[MAXN + 5], nxt[LOGA + 1];

vector<pii> qs[MAXN + 5];
ll ans[MAXM + 5];

class SegmentTree {
private:
	ll sum[MAXN * 4 + 5], tag[MAXN * 4 + 5];
	void push_down(int p, int l, int mid, int r) {
		if (tag[p]) {
			sum[p << 1] += tag[p] * (mid - l + 1);
			tag[p << 1] += tag[p];
			sum[p << 1 | 1] += tag[p] * (r - mid);
			tag[p << 1 | 1] += tag[p];
			
			tag[p] = 0;
		}
	}
	void push_up(int p) {
		sum[p] = sum[p << 1] + sum[p << 1 | 1];
	}
	void range_add(int p, int l, int r, int ql, int qr, ll v) {
		if (ql <= l && qr >= r) {
			sum[p] += v * (r - l + 1);
			tag[p] += v;
			return;
		}
		
		int mid = (l + r) >> 1;
		push_down(p, l, mid, r);
		
		if (ql <= mid) {
			range_add(p << 1, l, mid, ql, qr, v);
		}
		if (qr > mid) {
			range_add(p << 1 | 1, mid + 1, r, ql, qr, v);
		}
		
		push_up(p);
	}
	ll range_query(int p, int l, int r, int ql, int qr) {
		if (ql <= l && qr >= r) {
			return sum[p];
		}
		
		int mid = (l + r) >> 1;
		push_down(p, l, mid, r);
		
		ll res = 0;
		if (ql <= mid) {
			res = range_query(p << 1, l, mid, ql, qr);
		}
		if (qr > mid) {
			res += range_query(p << 1 | 1, mid + 1, r, ql, qr);
		}
		
		return res;
	}
public:
	void range_add(int l, int r, ll v = 1) {
		range_add(1, 1, n, l, r, v);
	}
	ll range_query(int l, int r) {
		return range_query(1, 1, n, l, r);
	}
	SegmentTree() {}
} T;

int main() {
	cin >> n >> m >> K;
	
	for (int i = 1; i <= K; ++i) {
		int x;
		cin >> x;
		good[x] = 1;
	}
	
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	for (int i = 1; i <= m; ++i) {
		int l, r;
		cin >> l >> r;
		qs[l].push_back(mk(r, i));
	}
	
	for (int i = n; i >= 1; --i) {
		vector<pii> events;
		for (int j = 0; j <= LOGA; ++j) {
			if ((a[i] >> j) & 1)
				nxt[j] = i; // [i, n] 里最小的, 第 j 位为 1 的位置
			if (nxt[j])
				events.push_back(mk(nxt[j], 1 << j));
		}
		events.push_back(mk(i, 0));
		sort(events.begin(), events.end());
		int cur_num = 0;
		for (int j = 0; j < SZ(events); ++j) {
			int jj = j;
			while (jj + 1 < SZ(events) && events[jj + 1].fi == events[j].fi)
				++jj;
			for (int t = j; t <= jj; ++t) {
				cur_num |= events[t].se;
			}
			
			if (good[cur_num % 10]) {
				int nxt_pos = ((jj == SZ(events) - 1) ? n + 1 : events[jj + 1].fi);
				T.range_add(events[j].fi, nxt_pos - 1);
			}
			
			j = jj;
		}
		for (int j = 0; j < SZ(qs[i]); ++j) {
			ans[qs[i][j].se] = T.range_query(i, qs[i][j].fi);
		}
	}
	for (int i = 1; i <= m; ++i) {
		cout << ans[i] << endl;
	}
	return 0;
}

day11-全国高中 IO 联赛一试

算期望比较麻烦。可以先求和，再除以总方案数 (frac{n!}{prod_{j=1}^{k}c_j!})。

对于每种选项 (i)，考虑以它为答案的每道题，对总和的贡献。钦定这道题做对了，其他题随便填的方案数是 (frac{(n-1)!}{prod_{j=1}^{k}(c_j-[j=i])!})。这样的题有 (a_i) 道，所以答案就是：

[frac{sum_{i=1}^{k}a_ifrac{(n-1)!}{prod_{j=1}^{k}(c_j-[j=i])!}}{frac{n!}{prod_{j=1}^{k}c_j!}} ]

因为是小数运算，我们不可能直接算这么大的阶乘。所以需要化简式子，得到：

[sum_{i=1}^{k}frac{a_ic_i}{n} ]

直接算这个即可。时间复杂度 (O(k))。

代码略。

day11-纸条

由于官方题解写的非常好，所以我直接丢官方题解了。

download

day11-全国高中 IO 联赛二试

考虑已知点集，求最小生成树的方法。

任取一个点为根（不一定是点集里的点）。设点 (i) 到根的距离为 (d_i)。把点集里所有点，按 (d_i) 从小到大排序。令第一个点（(d_i) 最小的点）作为生成树的根。从第二个点开始，每次选当前点前面的、与当前点距离最小的点，作为当前点（在生成树上）的父亲，并把当前点加入生成树。

这种做法的正确性证明（简要思路）：

设按 (d_i) 从小到大排好序后，每个点的位置为 (p_i)。

只需要证明，存在一个生成树，满足以 (p_{ ext{root}}=1) 的点 ( ext{root}) 为根时，其他点都满足 (p_{fa(i)}<p_i)。其中 (fa(i)) 是点 (i) 在生成树上的父亲。

可以先任取一个最小生成树。然后取最大的、满足 (p_{fa(u)}>p_{u}) 的点 (u)。令 (fa(u):=fa(fa(u)))。可以证明，这样边权和一定不会变大。

并且由于 (u) 是最大的满足 (p_{fa(u)}>p_u) 的点，所以 (p_{fa(fa(u))}) 一定 (<p_{fa(u)})，因此有限次操作后，一定能消除所有 (p_{fa(u)}>p_u) 的点。

详细证明

根据这种方法，我们求出本题答案就比较简单了。

利用期望的线性性，考虑个点到它（生成树上）的父亲的距离，对答案的贡献。枚举这个点 (u)，把所有（按 (d_i) 排序后）排在 (u) 前面的点，按与 (u) 的距离排序。在这些点里，枚举 (u)（生成树上）的父亲 (v)，则所有排在 (v) 前面的点，都一定不能在点集里。算出这样的概率，乘以 (u,v) 之间的距离，加入答案。

时间复杂度 (O(n^2))。

day12-T2-枣子

题目链接

考虑某个正整数 (t)，它可以表示为 (x^y) ((y>1)) 的形式，当且仅当 (y) 是【 (t) 的所有质因子的次数】的约数。具体地，设分解质因数后 (t=p_1^{e_1}p_2^{e_2}cdots p_k^{e_k})，则 (y|gcd(e_1,e_2,dots,e_k))。设最大的、合法的 (y) 为 (g(t))，则 (g(t)=gcd(e_1,e_2,dots,e_k))，且所有其他的、合法的 (y) 都是 (g(t)) 的约数。

设 (y = g(a))，(a=x^y)。则原数 (a^{(b^c)}) 可以写成 (x^{(yb^c)})，且根据 (g) 函数的定义，(x) 不能再被表示为任何数的 (>1) 次幂。

我们先预处理一个 (dp(i))，表示一个形如 (u^i) 的数，有多少种表示方法。其中 (u) 将作为一个整体不再被拆解（不会被拆成任何数的 (>1) 次幂，你可以把 (u) 想象为上一段中的 (x) ）。DP 的转移是考虑最底下的数，是 (u) 的几次方。例如，最底下的数是 (u^j) （(j) 是 (i) 的约数），那么它的指数就应该是 (frac{i}{j})，并且这个指数还能继续被拆分，拆分它的方案数就是 (dp(g(frac{i}{j})))，所以 (dp(i) = sum_{j|i}dp(g(frac{i}{j})))。通过巧妙地枚举 (frac{i}{j})（例如将 (i) 分解质因数后 dfs），我们可以顺便知道(g(frac{i}{j}))。设 DP 数组长度为 (L)，这个 DP 复杂度是 (O(Lsqrt{L})) 的。

理论上，只要这个 DP 数组的大小高达 (yb^c) 这么大，我们就能直接报出答案。（不过答案并不是 (dp(yb^c))，因为题目要求枣子塔高度 (geq 3)，而我们 DP 时并没有考虑这个要求。不过这并不本质，只要稍微修改一下 DP 的定义就能解决这一问题）。

但显然，DP 数组不可能有 (yb^c) 这么大，所以这个算法还需改进。

考虑最终的结果（也就是这个等于 (a^{(b^c)}) 的枣子塔）里，最底下的数是什么。发现它一定可以被表示为 (x^k)，其中 (k) 是 (yb^c) 的一个约数。如果枚举了 (k)，此时的方案数就是：堆出值等于 (frac{yb^c}{k}) 的、高度 (geq 2) 的枣子塔的方案数，也就是 (dp(g(frac{yb^c}{k})) - 1)。其中 (-1) 是去掉唯一的那个高度为 (1) 的枣子塔。

于是答案就等于：(sum_{k|yb^c}left(dp(g(frac{yb^c}{k})) - 1 ight))，令 (i = frac{yb^c}{k})，则也可以更简洁地写成：

[ ext{ans}=sum_{i|yb^c}left(dp(g(i)) - 1 ight) ]

虽然 (yb^c) 极大，它的约数也极多，但将它分解质因数却并不困难，我们只要把 (y) 和 (b) 分别分解质因数，再合并起来即可。

知道了它的质因数构成后，我们枚举 (g(i)) 的值，设为 (j)（显然 (j) 小于等于 (yb^c) 质因子的最大次数，也就是 (O(log y+clog b)) ），此时 (i) 里所有质因子次数，都必须是 (j) 的倍数，那我们枚举每个质因子 (p_t)，设它的出现次数为 (e_t)，则方案数是 (prod_{t}(lfloorfrac{e_t}{j} floor +1 ))。但这还包含了 (g(i)) 是 (j) 的倍数的情况，将它们减掉即可：暴力枚举倍数，总复杂度是调和级数，这是个经典套路了。

因为 (g(i)) 的值不超过 (O(log y + clog b)=O(loglog a + c log b))，所以 DP 数组也只需要预处理这么长。设 (L = clog b)，则该算法的总时间复杂度是 (O(Lsqrt{L} +TLlog L))。可以通过本题。

参考代码：

//problem:nflsoj480
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 3e4, LOG = 20;
const int MAXG = (MAXN + 1) * LOG;
const int MOD = 998244353;
inline int mod1(int x) { return x < MOD ? x : x - MOD; }
inline int mod2(int x) { return x < 0 ? x + MOD : x; }
inline void add(int &x, int y) { x = mod1(x + y); }
inline void sub(int &x, int y) { x = mod2(x - y); }

int gcd(int x, int y) { return (!y) ? x : gcd(y, x % y); }

int a, b, c;
vector<pii> prm_a, prm_b;
vector<pii> decompose(int x) {
	vector<pii> p;
	for(int i = 2; i * i <= x; ++i) {
		if(x % i == 0) {
			p.pb(mk(i, 0));
			while(x % i == 0) {
				x /= i;
				p.back().se++;
			}
		}
	}
	if(x != 1) {
		p.pb(mk(x, 1));
	}
	return p;
}

int dp[MAXG + 5];
void dfs(int idx, int g, int v, int id, const vector<pii>& p) {
	if(idx == SZ(p)) {
		if(v > 1) {
			add(dp[id], dp[g]);
		}
		return;
	}
	int vv = v;
	for(int i = 0; i <= p[idx].se; ++i) {
		dfs(idx + 1, gcd(g, i), vv, id, p);
		vv *= p[idx].fi;
	}
}
void init() {
	dp[1] = 1;
	for(int i = 2; i <= MAXG; ++i) {
		dp[i] = 1;
		vector<pii> p = decompose(i);
		dfs(0, 0, 1, i, p);
	}
	// cerr << "yes" << endl;
	// for(int i = 1; i <= 10; ++i) cerr << dp[i] << " "; cerr << endl;
}
int w[MAXG + 5];
void solve_case() {
	cin >> a >> b >> c;
	prm_a = decompose(a);
	prm_b = decompose(b);
	int g = prm_a[0].se;
	for(int i = 1; i < SZ(prm_a); ++i) g = gcd(g, prm_a[i].se);
	
	vector<pii> tmp = decompose(g);
	vector<pii> p;
	int i = 0, j = 0;
	while(i < SZ(tmp) && j < SZ(prm_b)) {
		if(tmp[i].fi == prm_b[j].fi) {
			p.pb(mk(tmp[i].fi, tmp[i].se + prm_b[j].se * c));
			++i; ++j;
		} else if(tmp[i].fi < prm_b[j].fi) {
			p.pb(mk(tmp[i].fi, tmp[i].se));
			++i;
		} else {
			p.pb(mk(prm_b[j].fi, prm_b[j].se * c));
			++j;
		}
	}
	while(i < SZ(tmp)) {
		p.pb(mk(tmp[i].fi, tmp[i].se));
		++i;
	}
	while(j < SZ(prm_b)) {
		p.pb(mk(prm_b[j].fi, prm_b[j].se * c));
		++j;
	}
	int lim = 0;
	for(int j = 0; j < SZ(p); ++j) {
		assert(p[j].se <= MAXG);
		ckmax(lim, p[j].se);
	}
	
	for(int i = 1; i <= lim; ++i) {
		w[i] = 1;
		for(int j = 0; j < SZ(p); ++j) {
			w[i] = (ll)w[i] * (p[j].se / i + 1) % MOD;
		}
		sub(w[i], 1);
	}
	int ans = 0;
	for(int i = lim; i >= 2; --i) {
		for(int j = i + i; j <= lim; j += i) {
			sub(w[i], w[j]);
		}
		// if(w[i]) cerr << i << " " << w[i] << endl;
		ans = ((ll)ans + (ll)w[i] * mod2(dp[i] - 1)) % MOD;
	}
	cout << ans << endl;
}
int main() {
//	freopen("jujube.in", "r", stdin);
//	freopen("jujube.out", "w", stdout);
	init();
	int T; cin >> T; while(T--) {
		solve_case();
	}
	return 0;
}

day12-T3-开关

题目要求的是集合数量，也就是忽略顺序的。不过由于题目强制了 (m) 次操作互不相同，我们可以先求出带顺序的答案，再除以 (m!) 。具体来说，记原答案是 (f_m(v))，我们令 (g_m(v) = m!f_m(v))，现在考虑 (g_m(v)) 怎么求。

考虑枚举前 (m-1) 个是啥，那么最后一个也就确定了。这样方案数是 ({2^nchoose m-1}(m-1)!)。

但这样可能会计算到一些不合法的情况，也就是我们的最后一次操作，和前面某个操作相等。那么由于这两个操作相等，它们异或和为 (0)，所以其他的 (m-2) 个操作的异或和就是我们想要的值（前 (v) 位为 (1) 的这个二进制数），并且这 (m-2) 个操作一定互不相等（因为是通过组合数 ({2^nchoose m-1}) 选出来的）。也就是说，这 (m-2) 个操作，形成了一个子问题，它们的方案数就是：(g_{m-2}(v))。

如果枚举，最后一次操作和前面哪次操作相等，那么不合法的总方案数就是：((m-1)(2^n-(m-2))g_{m-2}(v))。其中 (m-1) 是枚举哪次操作相等，((2^n-(m-2))) 是这两个操作可以选择的值（不能和其他 (m-2) 个操作相同），最后其他操作的方案数就是 (g_{m-2}(v))。

预处理出 ({2^nchoose 0},{2^nchoose 1},{2^nchoose 2},dots ,{2^nchoose m}) 的值，然后就能 (O(m)) 递推了。

总时间复杂度 (O(Tm))。

参考代码：

//problem:nflsoj481
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXM = 1000;
const int MOD = 19260817;
inline int mod1(int x) { return x < MOD ? x : x - MOD; }
inline int mod2(int x) { return x < 0 ? x + MOD : x; }
inline void add(int &x, int y) { x = mod1(x + y); }
inline void sub(int &x, int y) { x = mod2(x - y); }
inline int pow_mod(int x, int i) {
	int y = 1;
	while(i) {
		if(i & 1) y = (ll)y * x % MOD;
		x = (ll)x * x % MOD;
		i >>= 1;
	}
	return y;
}
int fac[MAXM + 5], ifac[MAXM + 5], inv[MAXM + 5];
void facinit() {
	fac[0] = 1;
	for(int i = 1; i <= MAXM; ++i) fac[i] = (ll)fac[i - 1] * i % MOD;
	ifac[MAXM] = pow_mod(fac[MAXM], MOD - 2);
	for(int i = MAXM - 1; i >= 0; --i) ifac[i] = (ll)ifac[i + 1] * (i + 1) % MOD;
	for(int i = 1; i <= MAXM; ++i) inv[i] = (ll)ifac[i] * fac[i - 1] % MOD;
}


int n, m, v;
int _2n, comb_2n[MAXM + 5]; // C(2^n, 1...m)
int ans[MAXM + 5];
void case_init() {
	// 已知 m,n 
	comb_2n[0] = 1;
	_2n = pow_mod(2, n);
	for(int i = 1; i <= m; ++i) {
		comb_2n[i] = (ll)comb_2n[i - 1] * mod2(_2n - i + 1) % MOD * inv[i] % MOD;
	}
}
void solve_case() {
	cin >> n >> m >> v;
	case_init();
	ans[0] = (!v);
	ans[1] = 1;
	for(int i = 2; i <= m; ++i) {
		ans[i] = mod2((ll)comb_2n[i - 1] * fac[i - 1] % MOD - (ll)ans[i - 2] * mod2(_2n - (i - 2)) % MOD * (i - 1) % MOD);
	}
	int Ans = (ll)ans[m] * ifac[m] % MOD;
	cout << Ans << endl;
}
int main() {
	facinit();
	int T; cin >> T; while(T--) {
		solve_case();
	}
	return 0;
}

day12-A

题目链接

考虑 (S) 和 (T) 从前往后第一个不同的位置 (x)，以及从后往前第一个不同的位置 (y)。一个核心的观察是，如果存在合法的翻转方案，最短的翻转串一定就是 ([x,y])。并且其他翻转串一定都是 ([x-i, y+i]) 的形式，且 (i) 是 (0,1,dots) 连续的一段。如果知道了 (S,T) 的哈希情况，这个最大的 (i) 我们可以二分出来。

可以用线段树维护哈希值，在线段树上二分。

注意特判 (S,T) 相等的情况，此时所有合法的翻转串，就是 (T) 里的回文串。由于 (T) 不会变，我们可以二分 + 哈希预处理出来。

时间复杂度 (O((|S| + m)log |S|))。

day15-T1-小 D 与原题

题目链接

相当于要把 ((1,2),(1,3),dots,(1,n),(2,3),(2,4),dots,(2,n),dotsdots,(n-1,n)) 这 (frac{n(n-1)}{2}) 对元素，分成 (n-1) 组，使得每组不出现重复的数字。

首先，((1,2),(1,3),dots,(1,n))，这 (n-1) 对元素中，任意两对都不可能出现在同一组（因为它们都有 (1)），所以不妨先将它们分别放在每一组的第一个。

现在，每一组还剩 (n-2) 个数字（即 (frac{n-2}{2}) 对元素）要放。对于第 (i) 组（也就是第一对元素为 ((1,i)) 的组），我们维护两个指针 (x,y)，初始时都等于 (i)。每次构造下一对数字前，令 (x) 往前移动一步，(y) 往后移动一步。具体来说：

[x' = egin{cases} x-1 && ext{if }x>2\ n && ext{if }x=2 end{cases} ]

[y' = egin{cases} y + 1 && ext{if }y < n\ 2 && ext{if }y =n end{cases} ]

这样它们最终会各自走 (frac{n-2}{2}) 步，恰好经过所有 (n-2) 个数字。相当于两个人，从同一起点出发，分别顺时针、逆时针走一个半圆，最后拼成一个整圆。所以肯定同一组里，一定不会经过重复的数字。

另外，可以发现，同一组里的每一对 ((x,y))，在半圆上的对称点相等（就是出发时的 (i)），不同组则不等。也可以用公式表示为，每一组具有一个唯一的 (((x-2)+(y-2))mod(n-1)) 的值。所以不同组里，一定不会出现同一对 ((x,y))。

综合上述两点，我们的构造方案是正确的。

参考代码（片段）：

int main() {
	int n; cin >> n;
	int len = n / 2 - 1;
	for(int i = 2; i <= n; ++i) {
		int x = i, y = i;
		cout << 1 << " " << x << " ";
		for(int j = 1; j <= len; ++j) {
			x = (x == 2 ? n : x - 1);
			y = (y == n ? 2 : y + 1);
			cout << x << " " << y << " ";
		}
		cout << endl;
	}
	return 0;
}

day15-T2-小 D 与随机

day15-T3-小 D 与游戏

特判 (nleq 3) 的情况。以下只讨论 (ngeq4)。

考虑把原串里 (a,b,c) 分别换成数字 (0,1,2)。发现每次操作字符串所有位上数字的和在 (mod 3) 意义下不变。那是不是所有数字和 (mod3) 相等的串，都能通过若干次操作相互达到呢？带着这个疑问，我们爆搜出 (n=4) 的情况。发现可以分成三类：

如果整个串所有字符都相等（即 (S_1=S_2=S_3=S_4)），那么它不能做任何变化，所以答案是 (1)。
除第 1 类外，如果存在一对相邻的字符相等，则答案是 (19)。
如果不存在一对相邻的字符相等，则答案是 (20)。

这比较好解释，因为如果不存在相邻、相等的字符，那这个串一定不是通过操作得到的（因为只要经过了操作，就一定存在相邻、相等的字符），所以这样的串答案比其他串多了一个它自己的初始状态。

又注意到在 (n=4) 时，对于 (mod3) 的每个余数，串的总数只有 (1+18+8=27) 种（分别是上述三类串的数量）。所以对于 (n=4)，我们得到的结论是：

对于第 2 类的串，它能到达任意一个和它同余的，第 1 或第 2 类的串。

对于第 3 类的串，它能到达任意一个和它同余的，第 1 或第 2 类的串；不过由于还要算上它自己的初始状态，所以它的答案比第 2 类的串多 (1)。

当 (n>4) 时，可以通过打表验证或归纳证明，这个结论是正确的。

于是问题转化为求第 2 类串的数量，也就是：字符之和 (mod3) 与原串同余的、存在一对相邻字符相等的，串的数量。可以做一个简单 DP。设 (dp[i][xin{0,1,2}][yin{0,1,2}][zin{0,1}])，表示考虑了前 (i) 位，最后一位是 (x)，字符之和 (mod3) 是 (y)，是否已经存在一对相邻、相等的字符，这样的串的数量。

时间复杂度 (O(n))。

参考代码（片段）：

const int MAXN = 2e5;
const int MOD = 998244353;
inline int mod1(int x) { return x < MOD ? x : x - MOD; }
inline int mod2(int x) { return x < 0 ? x + MOD : x; }
inline void add(int &x, int y) { x = mod1(x + y); }
inline void sub(int &x, int y) { x = mod2(x - y); }

int n, dp[MAXN + 5][3][3][2];
char s[MAXN + 5];

map<vector<int>, bool> mp;
void dfs(const vector<int>& v) {
	if(mp.count(v)) return;
	mp[v] = 1;
	for(int i = 0; i <= SZ(v) - 2; ++i) if(v[i] != v[i + 1]) {
		int x = 0;
		for(; ; ++x) {
			if(x != v[i] && x != v[i + 1]) break;
		}
		vector<int> vv = v;
		vv[i] = vv[i + 1] = x;
		dfs(vv);
	}
}
int main() {
	cin >> (s + 1);
	n = strlen(s + 1);
	if(n <= 3) {
		vector<int> st;
		for(int i = 1; i <= n; ++i) {
			st.pb(s[i] - 'a');
		}
		dfs(st);
		cout << mp.size() << endl;
		return 0;
	}
	bool all_same = true;
	for(int i = 2; i <= n; ++i) all_same &= (s[i] == s[1]);
	if(all_same) { cout << 1 << endl; return 0; }
	
	dp[1][0][0][0] = dp[1][1][1][0] = dp[1][2][2][0] = 1;
	for(int i = 2; i <= n; ++i) {
		for(int j = 0; j < 3; ++j) {
			for(int k = 0; k < 3; ++k) {
				for(int l = 0; l <= 1; ++l) if(dp[i - 1][j][k][l]) {
					for(int c = 0; c < 3; ++c) {
						add(dp[i][c][(k + c) % 3][l | (c == j)], dp[i - 1][j][k][l]);
					}
				}
			}
		}
	}
	int sum = 0;
	for(int i = 1; i <= n; ++i) sum += (s[i] - 'a');
	sum %= 3;
	int ans = 1;
	for(int i = 2; i <= n; ++i) if(s[i] == s[i - 1]) { ans = 0; break; }
	for(int j = 0; j < 3; ++j) add(ans, dp[n][j][sum][1]);
	cout << ans << endl;
	return 0;
}