【2024暑假集训ACM2】G.Competition 做题记录

对于一个 $01$ 序列，其得分计算方式如下：

• 令 $v=0,w=1$；
• 从前往后依次遍历序列，设当前位为 $x$：
  • $x=0$：$v\to v-1$；
  • $x=1$：先 $v\to v+2$，再 $w\to w\times v$；

求所有有 $n$ 个 $1$，$m$ 个 $0$ 的 $01$ 序列的得分和，对 $998244353$ 取模。

$1\le n\le 2\times 10^5$，$0\le m\le 10^9$。

转化为格路计数问题：

每一步从 $(x,y)$ 走到 $(x+1,y)$ 或 $(x,y+1)$。

• 从 $(x,y)$ 走到 $(x+1,y)$ 会让路径权值乘上 $2x-y+2$；
• 从 $(x,y)$ 走到 $(x,y+1)$ 会让路径权值乘上 $1$；

求从 $(0,0)$ 走到 $(n,m)$ 的所有路径权值之和。

考虑把每一步转移放入序列 $a$ 中，$x+1$ 为 $1$，否则为 $0$，则对于每个 $a_i$：

• $a_i=1$：
  • $i$ 和它前面的每个 $1$ 都会造成 $2$ 的贡献，故其可以和前面的每个 $1$ 连权值为 $2$ 的无向边 ；
  • $i$ 和它前面的每个 $0$ 都会造成 $-1$ 的贡献，故其可以和前面的每个 $0$ 连权值为 $-1$ 的无向边；
  • $i$ 还会额外贡献 $2$ 的权值，故其可以和点 $0$ 连权值为 $2$ 的无向边；
• $a_i=0$ 则只能和点 $0$ 连权值为 $1$ 的无向边；

那么最终会形成以 $0$ 为根的父亲编号比儿子小的一棵树，并且除了点 $0$ 外其它点的儿子 $v$ 必定满足 $a_v=1$。

那么根据 $0$ 的每个儿子满足 $a_v=0$ 还是 $a_v=1$ 计算其子树的答案，最后 EGF 组合起来即可。

设 $f_n$ 表示 $a_{v}=0$ 且大小为 $n$ 的子树的边权积的和（包括 $(0,v)$ 这条边），$g_n$ 表示 $a_v=1$ 且大小为 $n$ 的子树的边权积的和（包括 $(0,v)$ 这条边），那么考虑最后一个点带来的贡献，有：

$f_n=f_{n-1}\times(2(n-2)-1)\\ g_n=g_{n-1}\times2(n-1)\\$

初值 $f_{0}=0,f_{1}=1,g_{0}=0,g_{1}=2$。

设 $F(x)$ 和 $G(x)$ 分别为 $f$ 和 $g$ 的 EGF，则答案即为 $\left[\frac{x^{n+m}}{(n+m)!}\right]\left(\frac{F(x)^m}{m!}e^{G(x)}\right)$。

注意到 $[x^0]F(x)=0$，所以 $F(x)$ 可以提出一个 $x$，答案变为 $\frac{{(m+n)!}}{m!}\left[x^{n}\right]\left(\left(\frac{F(x)}{x}\right)^me^{G(x)}\right)$。

进一步，注意到 $e^{G(x)}$ 也是很好求的，设 $[\frac{x^n}{n!}]e^{G(x)}=h_n$，则考虑最后一个点带来的贡献可以直接求出 $h$：

$h_{n}=h_{n-1}\times (2(n-1)+2)$

其中 $h_0=1,h_1=2$。

设 $h$ 的 EGF 为 $H(x)$，则答案即为 $\frac{{(m+n)!}}{m!}\left[x^{n}\right]\left(\left(\frac{F(x)}{x}\right)^mH(x)\right)$，可以直接 $O(n\log n)$ 算，或者直接快速幂做到 $O(n\log ^2n)$。