「FJWC2019」吃 - 概率和期望 + 点分治 + NTT + CDQ分治

给你一张$n$个点$m$条边的图，每次会随机选择一个还未删除的点 $v$，然后访问所有与 $v$ 连通的点，然后删除点 $v$ ，直至所有点都被删除。

求期望访问次数，答案对$998244353$取模

$n\le 10^5, m\in[n - 1, n]$

Links

FZOJ 192

Solution

Tree

先考虑树的情况

显然这个期望就是每种情况的概率和，又因为期望具有线性性，所以可以考虑两两点对对答案的贡献

有序点对$(x, y)$，树上路径长度为$c$（经过$c$个节点），对答案的贡献为$\frac{1}{c}$

若在访问$x$时，$y$能够被访问，则说明$x$到$y$的这条链还没有断

也就是说，在所有删点方案中，只要$x$在x到y这条链除了x之外的任意一个点被删除之前删除，就会产生贡献

这个概率就是在只考虑x到y这条链的任意排列方案时，钦定第一个为$x$的概率，即为$\frac{1}{c}$

所以我们只需要对每个$c$求出长度为$c$的路径条数

点分治 + NTT合并即可

这个用NTT合并的trick也不难理解

在点分治合并答案时，下标（其实就是深度）也是一个形如$i+j=k$的合并方式，且是乘法运算，所以可以用NTT优化

光以上的部分我就调了一年。。。

---

Base-Ring Tree

接下来考虑基环树，仍然是考虑点对$(x, y)$的贡献

• $(x, y)$在同一棵子树内：与树的计算方法相同

• $(x,y)$不在同一棵子树内：

  

  令$dep[x] + dep[y] = c$，则此时删除$x$时$x, y$仍联通的概率等于$x$在$a+c$个点中最先删除或在$b+c$个点中最先删除的概率（分别对应经过环的两侧）

  通过容斥我们可以得到此时贡献为$\frac{1}{a + c} + \frac{1}{b + c} - \frac{1}{a + b + c}$

  随便选一条边破环为链，用类似CDQ分治的分治方法 + NTT即可

  其实这个分治方法也类似于序列上的点分治，就是每次考虑过中点的贡献

总复杂度$O(n\log^2 n)$

具体实现上，可以先破环为链，对剩下的部分计算一次树情况的答案

这部分我们算出来的答案既包括了每个子树的答案，又包括了各个子树之间通过环上某一条路径的答案

例如，假设破的环在$a$部分中，那么我们相当于已经计算了$\frac{1}{b+c}$的答案了

那么我们只需要分治计算$\frac{1}{a+c}$和$\frac{1}{a+b+c}$的贡献了

这样代码写起来会比较方便，更具体的部分可以直接看代码了，自我感觉写得应该是比较容易理解的

Code

#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const int Mod = 998244353;
const int g = 3;
const int inf = 0x3f3f3f3f;

int N, M;
vector <int> G[Maxn];

namespace MATH
{
	inline void Add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

	inline int Pow (int a, int b)
	{
		int ans = 1;
		for (int i = b; i; i >>= 1, a = (LL)a * a % Mod) if (i & 1) ans = (LL)ans * a % Mod;
		return ans;
	}
}

using namespace MATH;

namespace Poly
{
	int n, rev[Maxn << 2], F[Maxn << 2], G[Maxn << 2], Wn[Maxn << 2], Wn_inv[Maxn << 2];

	inline void init (int maxn)
	{
		for (int i = 1; i <= maxn; i <<= 1) Wn[i] = Pow(g, (Mod - 1) / (i << 1)), Wn_inv[i] = Pow(Wn[i], Mod - 2);
	}

	inline void dft (int *A, int flag)
	{
		for (int i = 0; i < n; ++i) if (rev[i] < i) swap (A[i], A[rev[i]]); 

		for (int mid = 1; mid < n; mid <<= 1)
		{
			int wn = Wn[mid];
			if (flag < 0) wn = Wn_inv[mid];
			for (int i = 0; i < n; i += (mid << 1))
			{
				int W = 1;
				for (int j = i; j < i + mid; ++j, W = (LL)W * wn % Mod)
				{
					int a = A[j], b = (LL)W * A[j + mid] % Mod;
					A[j] = (a + b) % Mod, A[j + mid] = (a - b + Mod) % Mod;
				}
			}
		}

		int inv = Pow(n, Mod - 2);
		if (flag < 0) for (int i = 0; i < n; ++i) A[i] = (LL)A[i] * inv % Mod;
	}

	inline void mul (int *A, int N, int *B, int M, int *Ans)
	{
		n = 1; while (n <= N + M) n <<= 1;
		for (int i = 0; i < n; ++i) rev[i] = (rev[i >> 1] >> 1) + (i & 1 ? (n >> 1) : 0);
		for (int i = 0; i < n; ++i) F[i] = i <= N ? A[i] : 0;
		for (int i = 0; i < n; ++i) G[i] = i <= M ? B[i] : 0;

		dft (F, 1), dft (G, 1);
		for (int i = 0; i < n; ++i) F[i] = (LL)F[i] * G[i] % Mod;
		dft (F, -1);
		for (int i = 0; i <= N + M; ++i) Ans[i] = F[i];
	}
}

int Ans[Maxn];

namespace TREE
{
	int Vis[Maxn], size[Maxn];
	int root, min_size, now_size;

	inline void dfs_pre (int x, int f = 0)
	{
		size[x] = 1;
		for (int y : G[x])
		{
			if (y == f || Vis[y]) continue;
			dfs_pre (y, x);
			size[x] += size[y];
		}
	}

	inline void get_root (int x, int f = 0)
	{
/**/	int now = now_size - size[x];
		for (int y : G[x])
		{
			if (y == f || Vis[y]) continue;
			get_root (y, x);
			Chkmax (now, size[y]);
		}

		if (Chkmin (min_size, now)) root = x;
	}

	int Sum[Maxn], Buc_All[Maxn], Buc_Now[Maxn], max_dep;

	inline void get_dep (int x, int f, int dep = 1)
	{
		++Buc_Now[dep], Chkmax(max_dep, dep);
		for (int y : G[x])
		{
			if (y == f || Vis[y]) continue;
			get_dep (y, x, dep + 1);
		}
	}

	inline void calc (int x)
	{
		int n = 1; ++Ans[1];

		for (int y : G[x])
		{
			if (Vis[y]) continue;
			max_dep = 0, get_dep (y, x);
			Sum[1] = Buc_All[1] = 1;

			Poly :: mul (Buc_All, n, Buc_Now, max_dep, Sum);

			for (int i = 1; i <= n + max_dep; ++i) Add (Ans[i], 2ll * Sum[i] % Mod);

			Chkmax(n, max_dep + 1);
			for (int i = 2; i <= n; ++i)
				Buc_All[i] += Buc_Now[i - 1], Buc_Now[i - 1] = 0;
		}

		for (int i = 0; i <= n; ++i) Buc_All[i] = Buc_Now[i] = Sum[i] = 0;
	}

	inline void divide (int x)
	{
		root = x, min_size = inf;
		dfs_pre (x), now_size = size[x], get_root (x), x = root;

		calc (x); Vis[x] = 1;

		for (int y : G[x]) if (!Vis[y]) divide (y);
	}
}

namespace CIRCLE
{
	int Vis[Maxn], Stack[Maxn], top;
	int Circle[Maxn], len, In[Maxn];

	inline void find_circle (int x, int f = 0)
	{
		if (len) return ;
		Vis[x] = 1, Stack[++top] = x;

		for (int y : G[x])
		{
			if (y == f) continue;
			if (Vis[y] && !len)
			{
				while (Stack[top] != y) In[Stack[top]] = 1, Circle[++len] = Stack[top--];
				In[y] = 1, Circle[++len] = y;
				return ;
			}
			find_circle (y, x);
		}

		--top;
	}

	int n, m;
	int L[Maxn], R[Maxn], Sum[Maxn << 2];

	inline void get_dep (int x, int f, int dep, int op)
	{
		if (!op) ++L[dep], Chkmax(n, dep);
		else ++R[dep], Chkmax(m, dep);

		for (int y : G[x])
		{
			if (y == f || In[y]) continue;
			get_dep (y, x, dep + 1, op);
		}
	}

	inline void divide (int l, int r)
	{
		if (l == r) return ;

		int mid = l + r >> 1;

		n = m = 0;
		for (int i = l; i <= mid; ++i) get_dep (Circle[i], 0, i, 0);
		for (int i = mid + 1; i <= r; ++i) get_dep (Circle[i], 0, len - i + 1, 1);

		// l -> 0 ; n -> n - l
		// (len - r + 1) -> 0 ; m -> m - (len - r + 1)
/**/	Poly :: mul (L + l, n - l, R + (len - r + 1), m - (len - r + 1), Sum + l + (len - r + 1));

		for (int i = l + (len - r + 1); i <= n + m; ++i) Add (Ans[i], 2ll * Sum[i] % Mod);
		for (int i = l; i <= n; ++i) L[i] = 0;
		for (int i = (len - r + 1); i <= m; ++i) R[i] = 0;

		/********************************************************************************/

		n = m = 0;
		for (int i = l; i <= mid; ++i) get_dep (Circle[i], 0, 0, 0);
		for (int i = mid + 1; i <= r; ++i) get_dep (Circle[i], 0, 0, 1);

		Poly :: mul (L, n , R, m, Sum);

		for (int i = 0; i <= n + m; ++i) Add (Ans[len + i], Mod - 2ll * Sum[i] % Mod);
		for (int i = 0; i <= n; ++i) L[i] = 0;
		for (int i = 0; i <= m; ++i) R[i] = 0;

		divide (l, mid), divide (mid + 1, r);
	}

	inline void work ()
	{
		find_circle (1);
		
		int x = Circle[1], y = Circle[len];
		G[x].erase (find (G[x].begin(), G[x].end(), y));
		G[y].erase (find (G[y].begin(), G[y].end(), x));

/**/	TREE :: divide (1);
		divide (1, len);
	}
}

inline void Solve ()
{
	Poly :: init (N << 1);

	if (M == N - 1) TREE :: divide (1);
	else CIRCLE :: work ();

	int ans = 0;
	for (int i = 1; i <= N; ++i) Add (ans, (LL)Ans[i] * Pow(i, Mod - 2) % Mod);

	//for (int i = 1; i <= N; ++i) cout << i << ' ' << Ans[i] << endl;

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>();

	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>();
		G[x].pb(y), G[y].pb(x);
	}
}

int main()
{

	freopen("eat.in", "r", stdin);
	freopen("eat.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}