No Abstract.

T1

Des. & Sol.

构造一个恰好有$s$条三条边的链的树.

把两个菊花图拼一起, 再挂一条链.

1
2


T2

Des.

2018 EC-final J.

Sol.

纳什均衡. SA+分治.

TODO: 记得看吉老师讲题.

1
2


T3

Des.

给一个串, 每次挖掉一位, 把后面的接到前面, 问结尾为$d$的本质不同子序列个数.

Sol.

首先考虑怎么算本质不同子序列个数. 每一位除了当前字符是求和以外, 其他字符都是复制.

把转移写成矩阵, 只有字符集种. 如果要算区间的, 就把这些也求出逆矩阵.

但字符集大的时候还是太吃不消了. 发现矩阵是有特征的. 转移矩阵和逆矩阵都可以通过维护行上元素和或列上标记来快速转移. 每次$O(\sum)$. 转移矩阵长这样:

逆矩阵就是那一列1变成了-1.

矩阵是右乘, 逆矩阵要左乘. 具体的方法可以去网上找. 维护这两种矩阵的前缀积就行了.

原题是区间询问, 到这里就做完了.

对于这个题, 我们把询问离线挂到挖去的位置上, 倒序做, 回答询问后, 滚动地删去下一个元素, 并在最左侧乘上这个元素, 的矩阵.

这题也有在线做法, 因为代码不可读放弃了. (这是一个flag, 日后我必将因为这样的问题落后余人, 虽然现在已经落后了).

1
2