「HNCPC2019」一些题

现场打的时候全程端茶送水...

C. Distinct Substrings

Description

给出一个长度为$n$的字符集大小为$m$的串，对于$\forall i\in[1,m]$，求往字符串后面新增一个字符$i$后增加了多少本质不同的子串

$1\le n, m\le 10^6$

Solution

[字符串] [Hash]

考虑往后接上颜色$c$时，用$n+1$减去前面出现过的串

直接找到所有位置$i$，满足$S_i = c$，然后求出一个最大的$len$，满足$[i - len, i - 1]$能和$[n-len+1, n]$匹配

二分哈希即可

D. Modulo Nine

Description

求有多少长度为$n$的序列$a_i$满足

• $a_i\in [0, 9]$
• 满足$m$条限制$(l, r)$：要求

对$10^9+7$取模

$1\le n, m\le 50$

Solution

[动态规划]

限制即为要求区间内存在至少两个$3$的质因子

$dp[i][j][k]$表示到第$i$位，最近的两个质因子在$j, k$的位置的方案数

转移显然，讨论一下后一位填什么

G. 字典序

Description

给定 $n \times m$矩阵，构造长为 $m$ 的排列使得对矩阵的每一行按其顺序取下标排序后字典序按行数非降，并且排列字典序尽量小

$n, m\le 2000$

Solution

[贪心]

from zusuyu

---

自己的理解：

贪心地考虑，一开始就满足在这一位上全合法的列肯定能直接选，且一定是选字典序最小的

在选完这个后，在分界线上的行就“解放”了，限制放宽

如果某一列上所有的不合法的位置都“解放”了的话，那么它就可以选了

用堆维护

H. 有向图

Description

一张$n+m$个点的图，初始在$1$号点，每次在$i$号点的时候有$P_{i,j}$的概率走到$j$号点，保证$\forall i\in[n+1,n+m],P_{i,j}=[i=j]$

可以发现经过无限次行走后停留在前$n$号点上的概率是$0$，求停留在后$m$号点每个点的概率

Solution

[概率和期望]

把概率转化成期望来理解。。。

显然这里概率就是期望，而只有按期望来理解的话$f_1$的那个$+1$才解释得通

设$f_i$表示$i$的期望经过步数

高消即可

J. Parity of Tuples (Easy)

Description

给出$n$个$m$元组$(a_1,a_2,...,a_m)$，记$count(x)$表示有多少个$m$元组满足$\forall j\in[1,m],popcount(a_j\land x)$为奇数

求

Solution

[动态规划]

显然可以对每个$m$元组算答案，然后加起来

把$m$原组看成一个$k\times m$的$01$矩阵，相当于选出一些行向量做异或运算，要求结果为$2^{m}-1$

设$f[i][S]$表示处理到第$i$个向量，当前运算结果为$S$的方案数

$3^x$的部分也可以拆到二进制的每一位算贡献，算在$f$里即可