Codeforces Round #722 (Div. 1)

E. Mashtali and Hagh Trees

题目描述

点此看题

称一棵有向树为阿七树当且仅当满足如下条件：

• 这棵树的最长有向路径是长度 \(n\)
• 以点任意点 \(u\) 为端点的有向边不超过 \(3\) 条
• \(u,v\) 是朋友当且仅当 \(u\) 能到 \(v\) 或者 \(v\) 能到 \(u\)，树上任意两点要么是朋友要么有一个共同的朋友。

给定 \(n\)，问不同构的阿七树有多少个，答案模 \(998244353\)

\(1\leq n\leq 10^6\)

解法

这道题最好不要直接从有向树的角度入手，我们可以把树分层，有向边的起点划分在上层，终点划分在下层。

在这个分层图上考虑 \(u,v\) 是朋友的条件，发现总有一个根，满足它和上层能构成一棵树，它和下层也能构成一棵有向树。考虑最长有向路径长度是 \(n\) 的条件，就等价于这个分层图的高度是 \(n\)

那么我们确定根上面的树和根下面的树再用乘法原理即可，设 \(dp(i,j)\) 表示高度为 \(i\) 的树根节点度数是 \(j\) 的方案数，我们用最上面的根来统计某一棵树的答案，所以要强制上面树的深度为 \(2\)，上面树为空要特殊讨论，所以可以写出答案：

现在的问题变成了算 \(dp(i,j)\)，可以定义 \(f(i,j)\) 表示高度至少为 \(i\) 的树根节点度数是 \(j\) 的方案数，这个要好转移一些，假设子树一共有 \(x\) 中选法，那么相当于从中选出 \(j\) 个来组成这个树，由于要考虑同构问题我们对于相同的子树种类是不存在顺序的，这相当于 \(x\) 个非负整数的和为 \(j\)，方案数是 \({x+j-1\choose j}\)，至于 \(x\) 就是 \(\sum_{j=0}^2 f(i-1,j)\)，最后再差分回来即可。

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

#include 
const int M = 1000005;
const int MOD = 998244353;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,ans,dp[M][4],inv[4]={0,1,(MOD+1)/2,(MOD+1)/3};
int C(int n,int m)
{
	int r=1;
	if(n=1;i--)
		for(int j=0;j<=3;j++)
			dp[i][j]=(dp[i][j]-dp[i-1][j]+MOD)%MOD;
	for(int i=1;i<=n;i++)
		for(int j=2;j<=3;j++)
			for(int k=0;k<=3-j;k++)
				ans=(ans+dp[i][j]*dp[n-i][k])%MOD;
	for(int i=0;i<=3;i++)
		ans=(ans+dp[n][i])%MOD;
	printf("%lld\n",ans);
}

F. AmShZ Farm

题目描述

点此看题

\(a,b\) 都数组由 \([1,n]\) 中的数字组成，\(a\) 数组长度为 \(n\)，并且满足给任意元素加上任意非负数后能变成某个排列，\(b\) 数组长度为 \(k\)，满足 \(a_{b_1}=a_{b_2}=...=a_{b_k}\)（注意我们没有要求 \(a,b\) 数组的元素两两不同）

问有多少个本质不同的数组对 \((a,b)\)，答案取模 \(998244353\)

\(1\leq n\leq10^9,1\leq k\leq 10^5\)

解法

发现 \(a,b\) 两个数组的计数还算比较独立吧，我们先考虑 \(a\) 数组怎么计数。

设 \(c_i\) 为数字 \(i\) 的出现次数，则限制可以翻译为 \(\sum_{j=i}^{n} c_j\leq n-i+1\)，但是这样根本算不出来，因为这个限制牵扯到的东西太多了，我们想要更加独立的限制。

不妨把题目换个说法：我们有 \(n+1\) 个位置排成一排，有 \(n\) 个人要坐进来，第 \(i\) 个人一开始会到位置 \(a_i\)（\(1\leq a_i\leq n\)），如果位置已满就往编号大的位置走，如果最后剩下的位置是 \(n+1\) 的话就是一个合法的 \(a\) 序列。

这是一个经典的序列转等概率环模型（第二次见了），所以我们可以改写题目为：有 \(n+1\) 个位置排成一个环，有 \(n\) 个人要坐进来，第 \(i\) 个人一开始会到位置 \(a_i\)（\(1\leq a_i\leq n+1\)），如果位置已满就往右边走，如果最后剩下的位置是 \(n+1\) 的话就是一个合法的 \(a\) 序列。

因为是一个环并且初始到每个点的概率相同，所以每个点被空出来的概率也是相同的，不难发现方案数就是 \((n+1)^{n-1}\)

我们再深入下去剖析这个模型，对于每种合法的 \(a\) 序列都可以映射到 \(n\) 种不同的不合法序列，因为如果我们让 \(a_i\) 变成 \((a_i+x-1)\%(n+1)+1\)，那么空出的位置 \(t\) 会变成 \((x+t-1)\%(n+1)+1\)，由此引出一个重要的性质：对于这 \(n+1\) 个方案来说，数字的分布情况是不会改变的，所以我们可以统计出所有排列的答案再除以 \(n+1\)

\(a\) 数组差不多搞定了，我们来解决 \(b\) 数组的计数。

枚举数字 \(x\) 的出现次数 \(i\)，由于 \(x\) 有 \(n+1\) 种选择就自动除 \(n+1\)，所以可以写出答案式：

首先要观察式子再化简（官方题解不给推导过程差评），因为底数很大但是指数很小，所以使用斯特林反演：

这个式子最好固定的指数，所以我们把它带进 \(i^k\) 中：

这时候心理要有根弦（我要交作业），通常是用组合意义和二项式反演把式子化简的，因为要让 \(i\) 出现得尽量少，所以我们把 \({i\choose j}\) 中的 \(i\) 给换走，那么这可以用一个组合恒等式：

把这个式子带进去，再调整一下顺序：

要用二项式反演是需要从 \(0\) 开始枚举的，所以我们把 \(i\) 调整成 \(i-j\)：

这是个明显的二项式反演了，所以可以得到最后的结果。

上面的式子显然可以 \(O(n\log n)\) 算，现在的问题就是快速算第二类斯特林数了，\(S(n,m)\) 的组合意义是 \(n\) 个不同的小球放在 \(m\) 个相同盒子的方案数，要求盒子非空，所以我们容斥空盒子数量：

因为盒子是相同的所以要除以盒子的排列 \(\frac{1}{m!}\)，可以通过变形让它可以卷积：

随便卷一下就可以做到 \(O(n\log n)\)，所以总时间复杂度 \(O(n\log n)\)

#include 
#include 
using namespace std;
const int M = 300005;
const int MOD = 998244353;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
namespace poly
{
	int len,A[M],B[M],rev[M];
	int qkpow(int a,int b)
	{
		int r=1;
		while(b>0)
		{
			if(b&1) r=r*a%MOD;
			a=a*a%MOD;
			b>>=1;
		}
		return r;
	}
	void NTT(int *a,int len,int op)
	{
		for(int i=0;i>1]>>1)|((len/2)*(i&1));
			if(i0) c[i]=c[i-1]*(n-i+1)%MOD*poly::qkpow(i,MOD-2)%MOD;
	}
	poly::work(k+1,k+1,a,b,a);
	for(int i=0;i<=k;i++)
		ans=(ans+a[i]*c[i]%MOD*poly::qkpow(n+1,n-i)%MOD*fac[i])%MOD;
	printf("%lld\n",ans);
}