CSA R9

挑几道有意思的讲讲

E

考虑一种集合表示的方法,自然的想到单调不降序列
自然的会想到从前填数,但这样要记录序列之和,序列末,序列长,显然TLE
考虑另一种一一对应的生成方式,初始(k)长度全(0),然后每次将一个后缀全(+1),选择的后缀长度单调不降
考虑(+1)产生的增量,这与后缀和相关,记录一下
由于最后需要生成正整数集合,要减去存在(0)的情况,即最后一次操作的后缀长度小于(n)

F

(f_{l,r,len,v})(s_{[l,r]})内的子序列长度为(len)的在模(101)意义下为(v)
(f_{l,r,len,v}=f_{l+1,r,len,v}+f_{l,r-1,len,v}-f_{l+1,r-1,len,v}),然后再考虑进(s_{l}=s_{r})的转移
我们发现(10^4equiv 1(mod~101)),这样的意义在于一个子序列,所在位置模(4)相同的,乘的系数相同
(len)记录模(4)意义下的即可

原文地址:https://www.cnblogs.com/Grice/p/13124124.html