Comet OJ题目选做

发表于 | 更新于

如题

Comet OJ round6 D另一道树题

题目链接：https://www.cometoj.com/contest/48/problem/D?problem_id=2280

solution：设$f(n)$表示有多少种方案可以使得$n$步之后游戏不结束。答案即为$\sum_{i=0}^nf(i)$

我们在求一个$f(k)$的时候，我们可以考虑下面这种思想：将所有走$k$步后在汇聚在同一终点的点集称为一个等价类，那么$f(k)$即为所有等价类的$siz+1$的乘积并减去$n+1$（减去空集和只选一个点）

这些等价类是互相合并得到的，多个$k$步的等价类可能会合并成一个$k+1$步的等价类。等价类合并有两种，一是在$lca$处合并，二是所有深度小于$k$的节点都会变成一个$k$步的等价类，第二类等价类我们直接计算，主要考虑第一类等价类。

本人使用的是长链剖分，维护每个等价类被建立时的步数,当一个等价类用于合并时，相当于从被建立时的步数一直到现在合并时的步数减1这段贡献都要乘$siz+1$，相当于对$f$的区间乘法，直接在前缀积数组打标记，最后再计算即可。然后再进行合并，当前合并时的步数即为这个新的等价类被建立时的步数

最后要记得扫一遍根所在的链来更新$f$，然后直接扫前缀积函数就可以得到$f$并计算答案，配合线性求逆元直接做到$O(n)$

点击隐藏/显示代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
//by hdmmblz,长链剖分 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,i,x,v,f[200005],inv[200005],ans=0;
const ll mod=998244353;
struct hp
{
	ll siz,t;
}h,pb;
void add_eve(ll l,ll r,ll p)
{
	//printf("*%lld %lld %lld\n",l,r,p);
	if(l>r)return;
	f[l]=f[l]*(p+1)%mod;
	f[r+1]=f[r+1]*inv[p+1]%mod;
}
struct Tree
{
	ll n;
	vector<ll>dep,zs,siz,fr;
	vector<vector<ll>>s;
	vector<vector<hp>>dp;
	vector<hp*>hd;
	void build()
	{
		dep.resize(n+1);s.resize(n+1);
		zs.resize(n+1);siz.resize(n+1);
		hd.resize(n+1);fr.resize(n+1);
		dep[0]=-1;
		return;
	}
	void long_dec(int p,int f)
	{
		int i,v;
		dep[p]=dep[f]+1;fr[dep[p]]++;
		zs[p]=siz[p]=0;
		for(i=0;i<s[p].size();i++)
		{
			v=s[p][i];
			if(v==f)continue;
			long_dec(v,p);
			if(siz[v]+1>=siz[zs[p]]+1)
			{
				zs[p]=v;
				siz[p]=siz[zs[p]]+1;
			}
		}
	}
	void dfs_pre()
	{
		dp.push_back(vector<hp>());
		dp[0].resize(siz[1]+1);
		hd[1]=&dp[0][0];
	}
	void dfs(int p,int f)
	{
		int i,v,j;
		(*hd[p])=(hp){1,0};
		//printf("%d %lld %lld\n",p,zs[p],siz[p]);
		if(zs[p]==0)return;
		hd[zs[p]]=hd[p]+1;
		dfs(zs[p],p);
		for(i=0;i<s[p].size();i++)
		{
			v=s[p][i];
			if(v==f||v==zs[p])continue;
			dp.push_back(vector<hp>());
			dp[dp.size()-1].resize(siz[v]+1);
			hd[v]=&dp[dp.size()-1][0];
			dfs(v,p);
			for(j=0;j<siz[v]+1;j++)
			{
				h=*(hd[v]+j);
				add_eve(h.t,j,h.siz);
				pb=*(hd[p]+j+1);
				add_eve(pb.t,j,pb.siz);
				*(hd[p]+j+1)=(hp){h.siz+pb.siz,j+1};
			}
		}
		if(p==1)
		{
			for(i=1;i<siz[p]+1;i++)
			{
				h=*(hd[p]+i);
				//printf("%d %lld %lld\n",i,h.siz,h.t);
				add_eve(h.t,i-1,h.siz);
			}
		}
	}
	void prefr()
	{
		int i;
		add_eve(0,0,fr[0]);
		for(i=1;i<=n;i++)fr[i]+=fr[i-1],add_eve(i,i,fr[i]);
	}
}T;
int main()
{
	inv[1]=1;f[0]=f[1]=1;
	for(i=2;i<=200004;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod+mod)%mod,f[i]=1;
	scanf("%lld",&T.n);
	T.build();
	for(i=2;i<=T.n;i++)
	{
		scanf("%lld",&x);
		T.s[x].push_back(i);
		T.s[i].push_back(x);
	}
	T.long_dec(1,0);
	T.dfs_pre();
	T.dfs(1,0);
	T.prefr();
	ans=(ans+f[0]-T.n-1+mod)%mod;
	for(i=1;i<=T.n;i++)f[i]=f[i]*f[i-1]%mod,ans=(ans+f[i]-T.n-1+mod)%mod;
	printf("%lld\n",ans);
	return 0;
}

Comet OJ round 7 C 临时翻出来的题

给定一个$n$元数列$A$，值域$[1,n]$，合法的$n$元排列指的是这个排列$i\in[1,n],pos_i\neq a_i$，对于合法排列中的每个逆序对$i<j,pos_i>pos_j$，都会产生$|i-j||pos_i-pos_j|$的贡献，求所有合法排列的贡献之和。

$n\leq16$

这题并不太难，毕竟放在了$C$，只是我当时现场想出的是$O(n^6)$的算法，渐进意义上比标准题解的$O(n^22^n)$要优，所以记录一下。有趣的是，当$n=16$时，这两个算法的时间复杂度刚好相同。

指数级算法去看官方题解即可，这里我就只说说我的多项式时间的算法，其实也非常简单，就一句话：枚举$i,j,pos_i,pos_j​$，然后相当于询问有多少个合法排列可以把剩下的$n-2​$个数和位置配对，这里直接跑一个$O(n^2)​$的容斥背包即可。

点击隐藏/显示代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,i,j,k,r,t,_,fac[17],p[17],u,v,ans=0,a[17],dp[17],nw,sum=0;
int main()
{
	fac[0]=1;
	for(i=1;i<=16;i++)fac[i]=fac[i-1]*i;
	scanf("%lld",&t);
	for(_=1;_<=t;_++)
	{
		scanf("%lld",&n);ans=0;
		for(i=1;i<=n;i++)a[i]=0;
		for(i=1;i<=n;i++)scanf("%lld",&p[i]),a[p[i]]++; 
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				for(u=1;u<=n;u++)
				{
					for(v=1;v<u;v++)
					{
						if(p[u]==i||p[v]==j)continue;
						memset(dp,0,sizeof(dp));
						a[p[u]]--;a[p[v]]--;
						dp[0]=1;
						for(k=1;k<=n;k++)
						{
							if(a[k]==0)continue;
							if(k==i||k==j)continue;
							for(r=k;r>0;r--)dp[r]-=a[k]*dp[r-1];
						}
						sum=0;
						for(k=0;k<=n;k++)dp[k]*=fac[n-2-k],sum+=dp[k];
						//printf("%lld %lld %lld %lld %lld\n",i,j,u,v,sum);
						ans+=sum*(j-i)*(u-v);
						a[p[u]]++;a[p[v]]++; 
					}
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}
/*
1
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
*/