A. 矩阵

构造神题

如果对角线上都是0

这告诉我们相同的行列不能放在一起染色

所以我们二进制分组,每次拿出所有这一位为0的行和这一位为1的列,把他们染色就好了

会发现其实这样还是有些重复,考虑再精简

$C_{13,6}=1716>1500$

所以这告诉我们,如果我们给每个数一个六二进制位编码,他们是可以放得下的

然后我们每次只需要拿出来所有编号第i位为0的列和编号第i位为1的行,然后他们操作一次就好了

于是我们就可以变成一个13次操作的更劣的复杂度

然后考虑现在我们还有下面一行要为0怎么弄

考虑按照奇偶性分开,就是把所有的列都分开,然后合并所有相邻状态相同的行,能够得到两个大致为对角线都是0的矩阵

举例

分开后,对于奇数

对于偶数

合并上下相同的行,也就是说我们把他们分配编号的时候直接分成一组内,然后同时操作

然后再次调用我们上述的那个分编号后二进制分组的算法,就能得到13*2次操作的好成绩了

B. 字符串

考场上使用了区间本质不同的子串数做的/cy

考虑后缀树上的一条边对应的字符串,对于反串建立sam,这节点表示的显然就是他比fa多出来的部分

然后我们能知道,对于left集合一个元素 $l_i$ ,这个点表示的串是 $[l_i+a,l_i+b-1]$

然后考虑 $[l_i,l_i+a-1]$ 这个字符串在正串SAM上对应的节点,他在dag上一定有至少两条出边或者right集合中有n

因为如果两个条件都不满足,就说明这个节点的right集合要和 $[l_i,l_i+a]$ 代表的节点right集合完全相同,同理可知left集合完全相同,这个和反串sam上不同节点是矛盾的...

类似的, $[l_i,l_i+b-1]$

怎么说明是对的呢?

如果只有一条出边,说明只能走到一个后缀节点,同时那个后缀节点的fail还不是他,那么剩下那个节点也不可能会有,因为那个节点一定也在这个节点中

同时right还要不包括n,因为如果包括n可能导致我们没有一条出边

于是我们会发现反串后缀树上的一条边就对应了正串sam上两点间的路径!

于是我们会发现在正串sam上把这些点打标记,上面已经说明后缀树上一条边可以映射到一条路径,实际上对于一条这样的路径,假设起点代表的字符串形如 $[r_i-x+1,r_i-y]$ ,显然可以对应后缀树上 $x-y$ 条边,只要 $l_i$ 落在这个区间即可

然后我们会发现对于每条路径挂在结尾点上之后,直接对于每个结尾点新建sam,然后从后向前加字符就能完成这个点上每个询问了

复杂度是O(n)的

看了看题解的代码,感觉上他就是实现了一个本质不同的子串个数长度的那些串拿出来建立sam的计数啊....但是压缩了同一个l位置的查询....使得他们是一起回答的询问的

然后我们就发现对于正串的sam上任意一个节点,它对应的每条路径长度挂在结尾点上,每一个点挂的路径一定是该点对应字符串的一个后缀,然后又有x-y条边,那么那些有边的节点就只能被经过1次,也就是说我们每次扩展sam都能使均摊一条边被计算

瞎抄的题解,详情请见压缩后缀自动机与Sasha and Swag Strings解题报告一文

集合划分容斥

扩展拉格朗日反演学啥啊