20200920 训练赛题解

T1 排课表 简易题解

大力搜索即可

注意：先搜索第一节和最后一节会大大提升程序运行效率

根据容斥原理容易得知： 答案=（不考虑任何限制的方案数）-（违反限制a不考虑限制b的方案数）-（违反限制b不考虑限制a的方案数）+（同时违反限制a和限制b的方案数）

即： 整理化简得：

预处理阶乘，QuickPow求逆元即可

注意：

• int一时爽，溢出火葬场。

总复杂度：

T2 玉米田

题目大意:用 种颜色染一个 元环，要求相邻位置颜色不同，环不能旋转

部分分: 时， 这是一个很平凡的结论

， 很小时，可以考虑暴力搜索，时间复杂度 ， 为 级别时，暴力显然行不通了，那么我们考虑一个更简单的情况:

在这种情况下，答案显然是

为什么环上不行呢?因为第 号位置的可染颜色不一定是 ，而是取决于第 和第 号位置的颜色是否相同

那么我们来分类讨论:(记 个位置染 种颜色的方案数为 )

Case1: 第 和第 号位置的颜色相同

那么我们可以将第 ，， 号位置当成一个位置，且这个合并起来的位置的颜色 ，那么被夹在中间的 有 中染法

我们发现这样合并相当于将位置减小了两个，所以

Case2: 第 和第 号位置的颜色不同

那么我们可以将第 号位置删除，现在 号位置和第 号位置相邻，统计出的答案一定满足Case2，那么将第 号位置再加回来后有 种染法

我们发现这样相当于将位置删除了一个，所以

所以

复杂度

由于 为 级别，所以运用矩阵快速幂解决问题，复杂度

• 找规律也可AC

T3 评测机

这里规定 与 同阶，

Case 1 ~ 2：

暴力乘完分解即可

复杂度：乱搞

这么做的瓶颈是乘积会炸long long……

什么？你说乘积取模再分解？你可以回家了

Case 3 ~ 8：

先分解所有 。由于每个 都只有5个质因数，所以分解的复杂度只有 。把每个 的质因数及其幂次都存入一个数组c[N][5]中（其中c[i][0...4]分别表示 的分解中 、、、、 的幂次）。这步预处理的复杂度为

从 和 暴力向上跳，同时把经过的点的每个质因数的幂次都加到数组res[5]中。这样就算出了乘积的质因数分解

最后用约数和公式即可得出答案（不需要等比数列求和，甚至不需要快速幂。暴力即可）

复杂度总为

Case 9 ~ 14：

因为 的质因数只有 ，所以乘积中 的质因数也只有 ，即乘积一定是 的幂次

那么我们直接把 换成 ，问题就变成了《[模板] [LCA] 牧场行走》了。直接按照那道题的做法去倍增就好了。最后得到乘积的幂次 后答案就是

注意，这是点权和不是边权和。算 的公式是

Case 15 ~ 20：

沿用9 ~ 14组的做法。将每个数的分解存入结构体中（存入数组也可以，不过结构体可以直接重载乘除很方便）

算约数和用公式+等比数列求和即可

struct node{
	int c[5];
	inline node(){memset(c，0，sizeof(c));}
	inline node operator*(const node& p)const{
		node res;
		for(int i=0;i<5;++i)res.c[i]=c[i]+p.c[i];
		return res;
	}
	inline node operator/(const node& p)const{
		node res;
		for(int i=0;i<5;++i)res.c[i]=c[i]-p.c[i];
		return res;
	}
	inline ll sigma1(){
		ll res=1;
		for(int i=0;i<5;++i)res=res*(qpow(P[i]，c[i]+1)-1)%mod;
		return res*iP5%mod; //这里iP5=792475是(2-1)*(3-1)*(5-1)*(7-1)*(11-1)模20020421意义下的逆元。提前预处理出来即可。
	}
}dis[N];
inline node div(int x){
	node res;
	for(int i=0;i<5;++i)
		while(!(x%P[i]))x/=P[i]，++res.c[i];
	return res;
}

和倍增的想法类似。预处理 根到 经过的所有节点的积的分解

void dfs(int u){
	for(int i=0;fa[u][i];++i)
		fa[u][i+1]=fa[fa[u][i]][i];
	for(int i=0，sz=e[u].size();i<sz;++i){
		int v=e[u][i];
		if(v==fa[u][0])continue;
		fa[v][0]=u;
		dep[v]=dep[u]+1;
		dis[v]=dis[u]*div(a[v]);
		dfs(v);
	}
}

倍增的作用仍然仅有求……

inline int lca(int x，int y){
	if(dep[x]<dep[y])swap(x，y);
	int t=dep[x]-dep[y];
	for(int i=0;t;++i，t>>=1)
		x=t&1?fa[x][i]:x;
	if(x==y)return x;
	for(int i=17;~i;--i)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i]，y=fa[y][i];
	return fa[x][0];
}

乘除和加减的性质类似，所以

inline int dist(int x，int y){
	int f=lca(x，y);
	return (dis[x]*dis[y]/dis[f]/dis[fa[f][0]]).sigma1();
}

总复杂度为