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

C. Distinct Substrings

Description

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

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

Solution

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

直接找到所有位置ii,满足Si=cS_i = c,然后求出一个最大的lenlen,满足[ilen,i1][i - len, i - 1]能和[nlen+1,n][n-len+1, n]匹配

二分哈希即可

D. Modulo Nine

Description

求有多少长度为nn的序列aia_i满足

  • ai[0,9]a_i\in [0, 9]
  • 满足mm条限制(l,r)(l, r):要求

109+710^9+7取模

1n,m501\le n, m\le 50

Solution

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

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

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

G. 字典序

Description

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

n,m2000n, m\le 2000

Solution

from zusuyu

19-9-2


自己的理解:

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

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

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

用堆维护

H. 有向图

Description

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

可以发现经过无限次行走后停留在前nn号点上的概率是00,求停留在后mm号点每个点的概率

Solution

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

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

fif_i表示ii的期望经过步数

高消即可

J. Parity of Tuples (Easy)

Description

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

Solution

显然可以对每个mm元组算答案,然后加起来

mm原组看成一个k×mk\times m0101矩阵,相当于选出一些行向量做异或运算,要求结果为2m12^{m}-1

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

3x3^x的部分也可以拆到二进制的每一位算贡献,算在ff里即可