Skip to content

【计数】20261006C 特征值 笔记 ​

给定 m 和 k,对于每个 n<m 求出:所有长度为 n,值域为 [1,m] 的数组 a 的价值和。设 S(l,r)=(∑i=lrai)modm,价值定义为:

(min[l,r]⊆[1,n]min(S(l,r),m−S(l,r)))k

菜成傻逼了,又被简单计数秒杀了。

区间和问题考虑转换为前缀和,设 si=∑j=1iaj,则变为 (sr−sl−1)modm 和 (sl−1+m−sr)modm。

这个结构相当于有个长度为 m 的环,在环上选 n+1 个点,随意标号为 s0…n,构成一个序列,最近的两个点的距离即为这个序列的价值。

接着考虑对 s 进行计数,由于是 mink 结构,考虑枚举这个 min,一次性计算出 min=x 的答案。

按照转换,这相当于选 n+1 个点,两两间距离至少为 x,即相当于确定一个 (n+1) 项总和为 m 的序列,每项至少为 x,使用插板法可知答案为:

(m−(n+1)x+nn)

对于要求有一项恰好为 x 的限制,容斥即可。

最近更新