传话游戏 题解

传话游戏 题解

题目描述

初始时你有一个长度为 \(m\) 的字符串 $ S_1 $ ，然后你可以进行 $ n-1 $ 次操作，每次操作修改当前字符串，形如删掉其中某些元素（可以全删，也可以都不删）。第 \(i\) 次操作得到的字符串记为 $ S_{i+1} $ ，这样得到了由 \(n\) 的字符串形成的序列 \(S\) ，问有多少种本质不同的序列？（对 $ 10^9 + 7 $ 取模。）

$ 1 \le n \le 10^9 , 1 \le (S_1)_i \le m \le 200 $

关键结论

如果你是一个有经验的选手，你就会对初始的每个元素赋一个存活时间 $ t_i $ ，表示该元素至多在 $ t_i $ 时刻还没有被删除。

注意到当两个相同的元素相邻时，删除哪一个都没有区别，那么我们钦定先删除后一个（如果有先后顺序的话），即 $ i < j , t_i > t_j $ 。换言之，对于一个 \(i\) ，设 \(j\) 为满足 $ j > i , t_j > t_i $ 的最小的 \(j\) ，若 $ (S_1)_i = (S_1)_j $ ，那么这个序列就是非法的（与其他情况重复）。

现在我们断言，每个合法的序列 \(t\) ，一定对应着两两不同的序列 \(S\) ，两者构成双射，证明不难的。只要对序列 \(t\) 计数就是答案。

朴素实现

扔到笛卡尔树上跑DP，设 $ f_{l,r,x} $ 表示区间 $ [l,r] $ 的的最大值为 \(x\) （有相同的认为靠前的更大）。

转移时，枚举一个 $ mid $ 表示当前区间的最大值的位置。

\[f_{l,r,x} = \sum_{mid} [ (S_1)_{r+1} \neq (S_1)_{mid} ] \times \sum_{ i<x } \sum_{ j \le x } f_{l,mid-1,i} \times f_{mid+1,r,j} \]

解释一下，由于这是一个类似于笛卡尔树的结构，限制是根节点的左子树的右链上的元素均与根节点不同。转移时枚举最大值的位置，那对于区间 $ [l,r] $ 来说， $ t_{r+1} $ 一定大于其中的所有元素的存活时间，所以 $ (S_1){r+1} \neq (S_1) $ 是必要的，不然会出现不合法的转移。

前缀和优化一下，记 $ s_{l,r,x} = \sum_{ i \le x } f_{l,r,i} $ ，可以做到 $ O(m ^3 n ) $ 的优秀复杂度，答案即为 $ s_{1,m,n} $

	for(int k=1;k<=n;k++)f[l][r][k]=(f[l][r][k]+s[l][mid-1][k-1]*s[mid+1][r][k])%mod;

拉插优化

直接上结论，$ f_{l,r} $ 是一个关于 $ x $ 的 $ r-l $ 次多项式。

首先，若 $ f_{l,r} $ 是一个 \(k\) 次多项式，那么对其中的一项做前缀和，是一个等比数列求和的形式，所以 $ s_{l,r} $ 是一个 $ k+1 $ 次多项式。

当 $ l=r $ ，不妨认为是一个0次多项式。再根据上述转移方程，显然可以归纳证明 $ s_{1,m} $ 是 $ m+1 $ 次多项式。

求出前 $ m+1 $ 项值，最后朗格朗日差值求第 \(n\) 项，复杂度 $ O(m^4) $ ，常数小，可以过。