省选测试23

A. 盗梦空间

分析

每次查询时进行一次 \(bfs\) 可以做到 \(nq\) 的复杂度,结合链可以得到 \(30\) 分

正解是给询问点建立虚树

计算时前先求一次多源最短路

可以得到虚树上每一个点的答案,设为 \(dis\)

那么答案就由两部分组成

\(1\) 、虚树上节点在原树上的子树内的答案

这个答案要把当前点所有在虚树上连出去的儿子的答案去掉

设这个点为 \(x\),子树内的点为 \(son\)

那么 \(dis[son]=dis[x]+dep[son]-dep[x]\)

只要维护一个子树内 \(dep\) 的最大值就可以了

\(2\)、被虚树边覆盖的节点在原树上的子树内的答案

这个答案要把当前点在虚树边方向的一个儿子的答案去掉

设虚树边的父亲节点为 \(fa\) ,儿子节点为 \(son\),被该虚树边覆盖的某个节点为 \(x\),\(x\) 的一个合法的儿子节点为 \(u\)

如果 \(dis[fa]=dis[son]+dep[son]-dep[fa]\)

说明最短路是从儿子方向来的

那么 \(dis[u]=dis[son]+dep[son]+dep[u]-2dep[x]\)

也就是对于这条边上的所有被覆盖的节点 \(x\),查询 \(x\) 子树内最大的 \(dep[u]-2dep[x]\)

如果 \(dis[son]=dis[fa]+dep[son]-dep[fa]\)

说明最短路是从父亲方向来的

那么 \(dis[u]=dis[fa]+dep[u]-dep[fa]\)

也就是对于这条边上的所有被覆盖的节点 \(x\),查询 \(x\) 子树内最大的 \(dep[u]\)

如果两种情况都不满足,就算一下那个分界点是什么

分界点上面的肯定由父亲贡献答案,下面的肯定由儿子贡献答案

考虑如果去除某个节点的贡献

一个很巧妙的方法是把倍增数组的定义改为去掉当前节点后,当前节点到 \(2^k\) 级祖先的答案

然后就可以直接做了

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<set>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=2e5+5;
int h[maxn],tot=1,n,m;
struct asd{
	int to,nxt;
}b[maxn];
std::set<int> usd;
#define sit std::set<int>::iterator
void ad(rg int aa,rg int bb){
	usd.insert(aa),usd.insert(bb);
	b[tot].to=bb;
	b[tot].nxt=h[aa];
	h[aa]=tot++;
}
std::multiset<int> ans0[maxn];
int fa[maxn][22],ans1[maxn][22],ans2[maxn][22],dep[maxn],maxdep[maxn],dfn[maxn],dfnc,ans;
void dfs1(rg int now,rg int lat){
	maxdep[now]=dep[now]=dep[lat]+1;
	dfn[now]=++dfnc;
	fa[now][0]=lat;
	ans0[now].insert(dep[now]);
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		rg int u=b[i].to;
		if(u==lat) continue;
		dfs1(u,now);
		ans0[now].insert(maxdep[u]);
		maxdep[now]=std::max(maxdep[now],maxdep[u]);
	}
}
void dfs2(rg int now){
	if(fa[now][0]){
		ans0[fa[now][0]].erase(ans0[fa[now][0]].find(maxdep[now]));
		ans1[now][0]=*ans0[fa[now][0]].rbegin();
		ans2[now][0]=ans1[now][0]-2*dep[fa[now][0]];
		ans0[fa[now][0]].insert(maxdep[now]);
		for(rg int i=1;(1<<i)<=dep[now];i++){
			fa[now][i]=fa[fa[now][i-1]][i-1];
			ans1[now][i]=std::max(ans1[now][i-1],ans1[fa[now][i-1]][i-1]);
			ans2[now][i]=std::max(ans2[now][i-1],ans2[fa[now][i-1]][i-1]);
		}
	}
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		rg int u=b[i].to;
		if(u==fa[now][0]) continue;
		dfs2(u);
	}
}
int getlca(rg int xx,rg int yy){
	if(dep[xx]<dep[yy]) std::swap(xx,yy);
	rg int len=dep[xx]-dep[yy],bit=0;
	while(len){
		if(len&1) xx=fa[xx][bit];
		bit++,len>>=1;
	}
	if(xx==yy) return xx;
	for(rg int i=18;i>=0;i--){
		if(fa[xx][i]!=fa[yy][i]){
			xx=fa[xx][i],yy=fa[yy][i];
		}
	}
	return fa[xx][0];
}
int a[maxn],k,sta[maxn],tp;
bool cmp(rg int aa,rg int bb){
	return dfn[aa]<dfn[bb];
}
void insert(rg int now){
	rg int lc=getlca(now,sta[tp]);
	while(1){
		if(dfn[lc]>=dfn[sta[tp-1]]){
			if(lc!=sta[tp]){
				ad(sta[tp],lc),ad(lc,sta[tp]);
				if(lc!=sta[tp-1]) sta[tp]=lc;
				else tp--;
			}
			break;
		} else {
			ad(sta[tp],sta[tp-1]),ad(sta[tp-1],sta[tp]);
			tp--;
		}
	}
	sta[++tp]=now;
}
void buildtree(){
	std::sort(a+1,a+1+k,cmp);
	sta[tp=1]=1,usd.clear();
	if(a[1]!=1) sta[++tp]=a[1];
	for(rg int i=2;i<=k;i++) insert(a[i]);
	while(tp>1){
		ad(sta[tp],sta[tp-1]),ad(sta[tp-1],sta[tp]);
		tp--;
	}
}
int dis[maxn],vis[maxn],tim;
void cls(){
	for(rg sit it=usd.begin();it!=usd.end();++it){
		rg int now=*it;
		h[now]=-1,dis[now]=0x3f3f3f3f;
	}
	tot=1;
}
struct jie{
	int num,jl;
	jie(){}
	jie(rg int aa,rg int bb){
		num=aa,jl=bb;
	}
	friend bool operator <(const jie& A,const jie& B){
		return A.jl>B.jl;
	}
};
std::priority_queue<jie> q;
void dij(){
	tim++;
	for(rg int i=1;i<=k;i++) q.push(jie(a[i],0)),dis[a[i]]=0;
	while(!q.empty()){
		rg int now=q.top().num;
		q.pop();
		if(vis[now]==tim) continue;
		vis[now]=tim;
		for(rg int i=h[now];i!=-1;i=b[i].nxt){
			rg int u=b[i].to;
			if(dis[u]>dis[now]+std::abs(dep[u]-dep[now])){
				dis[u]=dis[now]+std::abs(dep[u]-dep[now]);
				q.push(jie(u,dis[u]));
			}
		}
	}
}
void getans1(rg int now,rg int len,rg int val){
	if(len<0) return;
	rg int bit=0;
	while(len){
		if(len&1){
			ans=std::max(ans,ans1[now][bit]+val);
			now=fa[now][bit];
		}
		len>>=1,bit++;
	}
}
int getans2(rg int now,rg int len,rg int val){
	if(len<0) return now;
	rg int bit=0;
	while(len){
		if(len&1){
			ans=std::max(ans,ans2[now][bit]+val);
			now=fa[now][bit];
		}
		len>>=1,bit++;
	}
	return now;
}
int getson(rg int now,rg int u){
	rg int len=dep[u]-dep[now]-1,bit=0;
	while(len){
		if(len&1) u=fa[u][bit];
		len>>=1,bit++;
	}
	return u;
}
void dfs(rg int now,rg int lat){
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		rg int u=b[i].to;
		if(u==lat) continue;
		ans0[now].erase(ans0[now].find(maxdep[getson(now,u)]));
		dfs(u,now);
		if(dep[u]-dep[now]>1){
			if(dis[u]==dis[now]+dep[u]-dep[now]){
				getans1(u,dep[u]-dep[now]-1,dis[now]-dep[now]);
			} else if(dis[now]==dis[u]+dep[u]-dep[now]){
				getans2(u,dep[u]-dep[now]-1,dis[u]+dep[u]);
			} else {
				rg int tmp=getans2(u,((dep[u]-dep[now])-(dis[u]-dis[now]))/2,dis[u]+dep[u]);
				getans1(tmp,dep[tmp]-dep[now]-1,dis[now]-dep[now]);
			}
		}
	}
	ans=std::max(ans,dis[now]+*ans0[now].rbegin()-dep[now]);
	for(rg int i=h[now];i!=-1;i=b[i].nxt){
		rg int u=b[i].to;
		if(u==lat) continue;
		ans0[now].insert(maxdep[getson(now,u)]);
	}
}
void solve(){
	buildtree();
	dij();
	ans=0;
	dfs(1,0);
	printf("%d\n",ans);
	cls();
}
int main(){
	memset(h,-1,sizeof(h));
	n=read(),m=read();
	rg int aa,bb;
	for(rg int i=1;i<n;i++){
		aa=read(),bb=read();
		ad(aa,bb),ad(bb,aa);
	}
	dfs1(1,0);
	dfs2(1);
	memset(h,-1,sizeof(h));
	memset(dis,0x3f,sizeof(dis));
	tot=1;
	for(rg int i=1;i<=m;i++){
		k=read();
		for(rg int j=1;j<=k;j++) a[j]=read();
		solve();
	}
	return 0;
}

B. 爱乐之城

分析

设 \(f[n]=\sum_{i=1}^ni\sum_{j=1}^n[gcd(i,j)=1]j,g[n]=\sum_{i=1}^n\sum_{j=1}^n\mu(ij)\)

那么

\(\begin{aligned}f[n]&=2\sum_{i=2}^ni\sum_{j=1}^i[gcd(i,j)=1]+1\\&=2\sum_{i=2}^n\frac{\phi(i)i^2}{2}+1\\&=\sum_{i=1}^n \phi(i)i^2 \end{aligned}\)

化成 \(phi\) 的那一步可以考虑对于每一个数 \(n\)

如果 \(gcd(i,n)=1\) ,那么必定存在 \(gcd(i,n-i)=1\)

每一对数的和都是 \(n\),一共有 \(\frac{phi(n)}{2}\) 对

\(\begin{aligned}g[n]&=\sum_{i=1}^n\sum_{j=1}^n\mu(i)\mu(j)[gcd(i,j)=1]\\&=\sum_{i=1}^n\sum_{j=1}^n\mu(i)\mu(j)\sum_{d|gcg(i,j)}\mu(d)\\&=\sum_{d=1}^n\mu(d)(\sum_{d|i}^n \mu(i))^2 \end{aligned}\)

\(f\) 可以线性筛,\(g\) 可以枚举因数预处理

暴力枚举集合就可以拿到 \(25\) 分

设 \(sum=\sum_{T\in S}g(gcd(T))\prod_{a\in T}f[a]\)

枚举 \(gcd(T)=d\),则

则 \(sum=\sum_dg(d)\sum_{T\in S}g[gcd(T)=d]\prod_{a\in T}f[a]\)

令 \(ans[d]=\sum_{T\in S}g[gcd(T)=d]\prod_{a\in T}f[a]\)

问题转化为求 \(ans[d]\)

构造 \(r[d]=\prod_{d|a_i}(f[a_i+1])-1\)

有点类似于生成函数

那么 \(r[d]=\sum_{d|i}ans[i]\)

莫比乌斯反演即可 \(ans[d]=\sum_{d|i}r[i]\mu[i/d]\)

\(sum=\sum_dg(d)\sum_{d|k}\mu(k/d)(\prod_{k|a_i}(f(a_i)+1)-1)\)

\(op=0\) 的可以直接去做

\(op=1\) 的考虑每次改变一个 \(k\),只会增加 \(\sum_{d|k}f(d)\mu(k/d)\)

把这个东西预处理一下就可以通过枚举因数来算了

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<vector>
#define rg register
inline int read(){
	rg int x=0,fh=1;
	rg char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=1e6+5,mod=998244353,inv2=499122177;
inline int delmod(rg int now1,rg int now2){
	return now1-=now2,now1<0?now1+mod:now1;
}
inline int addmod(rg int now1,rg int now2){
	return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
	return now1*=now2,now1>=mod?now1%mod:now1;
}
int n,m,op,a[maxn],sum,pri[maxn],mu[maxn],phi[maxn],f[maxn],g[maxn],s[maxn],pre[maxn];
bool not_pri[maxn];
std::vector<int> vec[maxn];
void xxs(){
    not_pri[0]=not_pri[1]=1;
	mu[1]=phi[1]=f[1]=1;
	for(rg int i=2;i<=m;i++){
		if(!not_pri[i]){
			pri[++pri[0]]=i;
			mu[i]=mod-1;
             phi[i]=i-1;
		}
		for(rg int j=1;j<=pri[0] && i*pri[j]<=m;j++){
			not_pri[i*pri[j]]=1;
			if(i%pri[j]==0){
                phi[i*pri[j]]=mulmod(phi[i],pri[j]);
                break;
			}
			mu[i*pri[j]]=mod-mu[i];
 			phi[i*pri[j]]=mulmod(phi[i],pri[j]-1);
		}
	}
    for(rg int i=2;i<=m;i++) f[i]=mulmod(phi[i],mulmod(i,i));
    for(rg int i=1;i<=m;i++) f[i]=addmod(f[i],f[i-1]);
    for(rg int i=1;i<=m;i++){
        for(rg int j=i;j<=m;j+=i){
            vec[j].push_back(i);
        }
    }
    for(rg int i=1;i<=m;i++){
        g[i]=g[i-1];
        for(rg int j=0;j<vec[i].size();j++){
            rg int u=vec[i][j];
            g[i]=delmod(g[i],mulmod(s[u],mulmod(s[u],mu[u])));
            s[u]=addmod(s[u],mu[i]);
            g[i]=addmod(g[i],mulmod(s[u],mulmod(s[u],mu[u])));
        }
    }
    for(rg int i=1;i<=m;i++){
        for(rg int j=i;j<=m;j+=i){
            pre[j]=addmod(pre[j],mulmod(g[i],mu[j/i]));
        }
    }
}
int ans[maxn],d[maxn];
int main(){
	n=read(),m=read(),op=read();
    xxs();
    for(rg int i=1;i<=n;i++) a[i]=read();
    for(rg int i=1;i<=m;i++) d[i]=1;
    for(rg int i=1;i<=n;i++){
        if(op) a[i]=(1LL*19891989*sum%m+a[i])%m+1;
        rg int tmp=a[i];
        for(rg int j=0;j<vec[tmp].size();j++){
            rg int u=vec[tmp][j];
            sum=delmod(sum,mulmod(d[u]-1,pre[u]));
            d[u]=mulmod(d[u],addmod(f[tmp],1));
            sum=addmod(sum,mulmod(d[u]-1,pre[u]));
        }
        if(op) printf("%d\n",sum);
	}
	if(!op) printf("%d\n",sum);
	return 0;
}

星际穿越

分析

对于 \(r=1,n \leq 17\) 的,状压随便打打就行了

对于 \(r=1,n\leq 2000\) 的

设 \(f[i][j]\) 为第 \(i\) 个数在前 \(i\) 个数的排名为 \(j\) 的方案数

枚举第 \(i+1\) 个数的排名即可

如果加上前缀和优化复杂度就是 \(n^2\)

考虑问题本质是什么

令 \(m=\frac{n-1}{k}\)

实际上就是恰好选择 \(m\) 段上升的子序列

恰好满足不是很好求,但是可以求出至少有多少个不满足的

答案就是至少有 \(0\) 个不满足的-至少有 \(1\) 个不满足的+至少有\(2\) 个不满足的 \(\cdots\)

设 \(f[i][j]\) 为当前考虑到 \(ik\) 这个位置,至多有 \(j\) 段上升子序列的方案数

因为我们没有去考虑两个上升子序列的交点处是什么样的,所以是至多

转移为 \(f[i][j]=\sum_{o=0}^{i-1}f[o][j-1]\frac{1}{(k(i-o))!}\)

阶乘那一部分就是一个可重排列,最后还要乘上一个 \(n!\)

那么最终的答案就是 \(n!\sum_{i=0}^m\sum_{j=0}^if[i][j](-1)^{i-j}\frac{(-1)^{m-i}}{(n-ki)!}\)

复杂度是 \(n^3\) 的

其实对于 \(r\) 不等于 \(1\) 的情况,任意两行之间选出上升子序列是互不影响的,所以转移的时候给阶乘来个 \(r\) 次方就行了

但是这不等价于给 \(r=1\) 时的答案求一个 \(r\) 次方

因为稳定每一行是都稳定

不稳定只要有一行不稳定就不稳定

所以不是简单的 \(r\)次方的关系

考虑如何化简这个 \(n^2\) 的 $dp $

可以发现第二维在转移的时候并没有用,只是在计算答案的时候乘了一个 \((-1)^{i-j}\)

我们可以把这个 \((-1)^j\) 提出来,转移的时候乘上一个 \(-1\),就能压掉一维

\(f[i]=-\sum_{j=0}^{i-1}\frac{f[j]}{(k(i-j))!}\)

答案为 \(n!\sum_{i=0}^mf[i](-1)^i\frac{(-1)^{m-i}}{(n-ki)!}=n!(-1)^m\frac{f[i]}{(n-ki)!}\)

这样复杂度就是 \(n^2\) 的

发现这个东西是一个卷积的形式,但是有依赖关系

分治 \(fft\) 的复杂度太高,所以考虑生成函数

设 \(F=\sum_{i=0}^{n}f[i]x,G=-\sum_{i=1}^m(n-ki)!\)

那么 \(F=F \times G+1\)

即 \(F=\frac{1}{1-G}\)

多项式求逆即可

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#define rg register
const int maxn=3e6+5,mod=998244353,G=3;
inline int delmod(rg int now1,rg int now2){
	return now1-=now2,now1<0?now1+mod:now1;
}
inline int addmod(rg int now1,rg int now2){
	return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
	return now1*=now2,now1>=mod?now1%mod:now1;
}
int n,r,k,f[maxn],ans=0,m,jc[maxn],jcc[maxn],ny[maxn];
int ksm(rg int ds,rg int zs){
	rg int nans=1;
	while(zs){
		if(zs&1) nans=mulmod(nans,ds);
		ds=mulmod(ds,ds);
		zs>>=1;
	}
	return nans;
}
void pre(){
	ny[1]=1;
	for(rg int i=2;i<=n;i++) ny[i]=mulmod(mod-mod/i,ny[mod%i]);
	jc[0]=jcc[0]=1;
	for(rg int i=1;i<=n;i++) jc[i]=mulmod(jc[i-1],i),jcc[i]=mulmod(jcc[i-1],ny[i]);
	for(rg int i=0;i<=n;i++) jc[i]=ksm(jc[i],r),jcc[i]=ksm(jcc[i],r);
}
int wz[maxn];
void ntt(rg int A[],rg int lim,rg int typ){
	for(rg int i=0;i<lim;i++) if(i<wz[i]) std::swap(A[i],A[wz[i]]);
	for(rg int len=1,t0=0;len<lim;len<<=1,t0++){
		rg int w0=ksm(G,(mod-1)/(len<<1));
		for(rg int j=0,now=len<<1;j<lim;j+=now){
			for(rg int k=0,w=1;k<len;k++,w=mulmod(w,w0)){
				rg int x=A[j+k],y=mulmod(A[j+k+len],w);
				A[j+k]=addmod(x,y),A[j+k+len]=delmod(x,y);
			}
		}
	}
	if(typ==-1){
		std::reverse(A+1,A+lim);
		rg int ny=ksm(lim,mod-2);
		for(rg int i=0;i<lim;i++) A[i]=mulmod(A[i],ny);
	}
}
int finv[maxn];
void getinv(rg int A[],rg int B[],rg int deg){
	if(deg==1){
		B[0]=ksm(A[0],mod-2);
		return;
	}
	getinv(A,B,(deg+1)>>1);
	rg int lim=1,bit=0;
	for(;lim<deg+deg;lim<<=1) bit++;
	for(rg int i=0;i<lim;i++) wz[i]=(wz[i>>1]>>1)|((i&1)<<(bit-1));
	for(rg int i=0;i<deg;i++) finv[i]=A[i];
	for(rg int i=deg;i<lim;i++) finv[i]=0;
	ntt(B,lim,1),ntt(finv,lim,1);
	for(rg int i=0;i<lim;i++) B[i]=mulmod(B[i],delmod(2,mulmod(B[i],finv[i])));
	ntt(B,lim,-1);
	for(rg int i=deg;i<lim;i++) B[i]=0;
}
int a[maxn];
int main(){
	scanf("%d%d%d",&n,&r,&k);
	pre();
	m=(n-1)/k;
	for(rg int i=1;i<=m;i++) a[i]=jcc[k*i];
	a[0]=1;
	getinv(a,f,m+1);
	for(rg int i=0;i<=m;i++) ans=addmod(ans,mulmod(f[i],jcc[n-k*i]));
	ans=mulmod(ans,jc[n]);
	ans=mulmod(ans,m&1?mod-1:1);
	printf("%d\n",ans);
	return 0;
}
上一篇:数据结构——分块:数列分块入门


下一篇:CF1100F Ivan and Burgers