发布于

lp4577 FJOI2018 领导集团问题

我们尝试类比序列上的情况来看这一题。

对于序列上的情况，我们维护一个集合 \(S\) ，其中 \(S_i\) 表示，长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么，对于新的点，我们考虑两种情况：它能加长序列，那么就加长；否则，就尽可能地更新最小值。

对于树上的情况，我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\)， 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点，能够构造的大小为 \(j\) 的集合的最小项的最大值。

如果我们把所有子节点的 \(S\) 都已经整合在一起了，那么更新根节点是比较容易的：类比于序列即可。 问题在于子节点要如何合并。

仔细观察，发现，子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。

怎么优化这个做法呢？ 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ，足以通过此题。 具体来说，我们对于每个节点开一个map，然后暴力合并。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
	sn[X]=0,sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
inline void dfs1(int X){
	if(sn[X]){
		dfs1(sn[X]);
		id[X]=id[sn[X]];
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v);
		lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
	}
	lst[id[X]].insert(w[X]);
	multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
	if(it!=lst[id[X]].begin()){
		--it;lst[id[X]].erase(it);
	}
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
		id[i]=i;
	}
	int x;
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		fa[i]=x;add(x,i);
	}
	dfs0(1);
	dfs1(1);
	printf("%d\n",lst[id[1]].size());
}
int main(){
	init();
	return 0;
}
发布于

lp4980 【模板】Polya定理

Polya定理是一个关于置换群中组合计数的定理。
首先我们来了解Burnside引理。这个引理的证明较为复杂，在这里仅介绍其内容。
Burnside引理的内容是这样的：在置换意义下本质不同的染色方案数，等于单个置换不会改变的染色方案数的平均值。
那么，单个置换不会改变的染色方案数要怎么求呢？我们不妨把置换关系建成一张图，那么这张图必然由若干个环构成。也就是说，对于同一种置换，可能存在若干个环，而每个初始状态就是环上的一个节点。Polya定理描述的就是，某一种置换不会改变的方案数，等于颜色数的「这个置换对应的循环节个数」

阐述了上述两个定理，现在我们来看这一题。
我们观察到，这个环上存在 n 种置换。对于置换 i 而言，它的循环大小是：
$$
\frac{n}{\gcd(n,i)}
$$
这也就意味着，它的循环个数是：
$$
\gcd(n,i)
$$
那么我们要求的答案就是：
$$
\frac{\sum_{i=1}^nn^{(n,i)}}{n}
$$
然而这样计算答案的复杂度是 O(n) 的，我们无法接受。
我们不妨考虑枚举这个公因子。那么，容易证明的是，每一个公因子d对应的置换个数是\(\varphi(\frac{n}{d})\)

这是因为， d 是 \(\frac{n}{d}\) 个数的因数，而这些数中，如果它和\(\frac{n}{d}\)存在公因子的话，那么它和n的最大公因数必然大于d。

所以，我们求的就是：
$$
\frac{\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}}}{n}=\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}-1}
$$
我们只要枚举n的因数即可。

然而求这里的 \(\varphi\) 倒可能存在一些问题。事实上，由于我们要取的因数的值域是 \(10^9\) ，我们无法使用欧拉筛来预处理，而需要现场做。

这样的复杂度是不是对的呢？它的最坏情况是 \(O(Tn^{\frac{3}{4}})\) 的，但由于我并不会分析的一些性质，它不会达到这个值。因此可以通过此题。

另：括号忘记加，爆O泪两行。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const int N=1000005;
inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;RT%=MOD;
		}
		A*=A;A%=MOD,X>>=1;
	}
	return RT;
}
int n;
inline int phi(int X){
	int RT=1;
	for(int i=2;i*i<=X;++i){
		if(X%i==0){
			X/=i;RT*=i-1;
			while(X%i==0){
				X/=i;RT*=i;
			}
		}
		if(X==1){
			break;
		} 
	}
	if(X>1){
		RT*=X-1;
	}
	return RT;
}
void init(){
	scanf("%d",&n);
	ll ans=0;
	for(int i=1;i*i<=n;++i){
		if(n%i==0){
			ans+=(1ll*phi(n/i)*pw(n,i-1))%MOD;
			if(i*i!=n){
				ans+=(1ll*phi(i)*pw(n,n/i-1))%MOD;
			}
			ans%=MOD;
//			printf("%d %lld\n",i,ans);
		}
	}
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}