Mr_Wu

题解 H Groundhog Speaking Groundhogish

题解

/ 注册

H Groundhog Speaking Groundhogish

597 浏览 0 回复 2020-08-08

Mr_Wu

+关注

Groundhog Speaking Groundhogish

https://ac.nowcoder.com/acm/contest/5674/H

H Groundhog Speaking Groundhogish

吐槽

~~多项式题居然多组数据，wsm？？？~~

~~我很不幸被卡常了 QQAQ~~

题意

字符集为 $\{1,2,\cdots,m\}$ ，每个字符有权值 $a_i$ 。

有一个未知串，我们知道了它的一个子序列是长度为 $n$ 的字符串 $s$ ，且未知串未知的字符数 $\le k$ 。一个串的权值为每个字符权值的乘积。

输出所有可能的未知串的权值和模 $998244353$ 。

数据范围： $1\le n,m\le 10^5, 0\le k\le 10^5, 0\le a_i<998244353, 1\le s_i\le m, 1\le T\le 250$ 。

至多 $7$ 组数据满足 $\max\{n,m,k\}\ge 10^4$ 。

题解

设 $f(i,j)$ 表示枚举完未知串的前 $i$ 位，匹配完了 $s$ 的前 $j$ 位，求答案。则

$f(i,j)=f(i-1,j-1)\times a_{s_j}+f(i-1,j)\times (S-a_{s_j})$

（其中 $S=\sum a_i$ ）初值为 $f(0,0)=1$ ，答案是 $\sum_{i=n}^{n+k} f(i,n)$ 。

然后我们考虑找找规律，那么打出一个表：(令 $A_j=a_{s_j},B_j=S-a_{s_j}$ )

（考试的时候我列到 $i=4$ 了，找出规律更加容易）我们发现 $f(i,j)$ 是 $A_1A_2\cdots A_j (从 B_0,B_1,\cdots,B_j 中选 i-j 个求乘积的和（可以选重）)$ 。

考虑证明这件事情，那么考虑数归：分类 $B_j$ 是否被选，如果没选那么就是 $A_jf(i-1,j-1)$ ，如果选了就是 $B_jf(i-1,j)$ 。

所以答案就是

$\begin{aligned} & ans=\left(\prod_{i=0}^n A_i \right) \sum_{i=0}^k [z^k] \prod_{j=0}^n \sum_{k\ge 0} (B_jz)^k \\ & = \left(\prod_{i=0}^n A_i \right)\sum_{i=0}^k [z^k] \prod_{j=0}^n \frac{1}{1-B_jz} \\ & = \left(\prod_{i=0}^n A_i \right)\sum_{i=0}^k [z^k] \frac{1}{\prod_{j=0}^n (1-B_jz)} \end{aligned}$

分母使用 $O(n\log^2 n)$ 的分治乘求出，然后 $O(k\log k)$ 求乘法逆。

时间复杂度 $O(n\log^2 n + k\log k)$ 。

举报

收藏

赞 7

评论加载中...