ARC129C 题解

发布时间 2023-08-14 13:34:01作者: liangbowen

problem & blog

提供一种不一样的做法喵。


考虑原问题的逆问题。这个很典,直接前缀和 \(sum_i\) 表示 \([1,i]\) 顺次拼接的数 \(\bmod 7\) 的值,那么 \([l,r]\) 符合条件当且仅当 \(sum_r-sum_{l-1}=0\),即 \(sum_r=sum_{l-1}\)

\(c_p=\sum\limits_{i=1}^n[sum_i=p]\),这个逆问题的答案即 \(\sum\limits_{i=0}^6 \dfrac{c_p\cdot(c_p-1)}2\)。所以对于原问题,只需要构造 \(7\) 个三角形数之和为 \(n\) 即可。这个限制也太宽啦,所以直接从大到小枚举三角形数,然后暴力构造都行。

代码又短又好写,所以不贴了,想看的自己去翻我的 Atcoder Submission。