20ZR提高组十联测 Day1

stone

将 $n$n 分成尽可能少的 $3k^2-3k+1 \quad(k \ge 1)$3k2−3k+1(k≥1) 的形式。

$1 \leq Q \leq 1000, 1 \leq n \leq 10^{11}$1≤Q≤1000,1≤n≤1011。

化简一下式子

$3k^2 - 3k+1 = 3k(k-1)+1 \\ = 6 \times \frac{k(k-1)}{2} + 1$3k2−3k+1=3k(k−1)+1=6×2k(k−1)​+1

打个 $\frac{k(k-1)}{2}$2k(k−1)​ 的表

找规律发现任意一个数都可以由三个形如 $\frac{n(n+1)}{2}$2n(n+1)​ 的数表示，当然你也可以由 $\ge 3$≥3 个这样的数表示，只需要拆出一个 $1$1。

可以猜测，如果 $n \bmod 6 \ge 3$nmod6≥3，那么答案就是 $n \bmod 6$nmod6，写个对拍可以发现就是这样。

如果 $n \bmod 6 = 0$nmod6=0，那么将它拆成 $n-1$n−1 和 $1$1，答案为 $5$5。

如果 $n \bmod 6 = 1$nmod6=1，如果能表示成 $3k^2 - 3k+1$3k2−3k+1 的形式，那么答案为 $1$1。否则拆出一个 $1$1 变成上一个情况，答案为 $7$7。

如果 $n \bmod 6 = 2$nmod6=2，显然可以拆出两个 $2$2 的，答案为 $8$8。但是它可能表示为两个形如 $3k^2 - 3k+1$3k2−3k+1 的形式。所以预处理一下，散列表可能超时，这个可以用双指针。

palindrome

求 $S$S 中形如 $aa^ra$aara 的子串个数，其中 $a^r$ar 代表 $a$a 的反串。

$1 \leq |S| \leq 2 \times 10^6$1≤∣S∣≤2×106

不能 kmp，不可能 Trie，SAM 又不属于 NOIp 考察范围，那么只有 hash 和 manacher。但 hash 能干的东西有点广泛。那么看看 manacher，也就是回文串。可以发现 $a\#a^r\#a$a#ar#a 长的挺像回文串，而且它确实有以两个 $\#$# 为回文中心的回文串。

那么先马拉车一下。然后枚举第一个 $\#$# 的位置，去统计第二个 $\#$# 的贡献。也就是求在第一个 $\#$# 的回文范围的右边，有多少个回文中心的左端点小于等于第一个 $\#$# 的位置。

数据真水，到这 $O(n^2)$O(n2) 暴力已经可以过了。可以发现这是一个二维偏序，数据范围有点大，直接小常数的树状数组维护水过去。

random

乘上一个 $n!$n! 就相当于对所有情况的答案求和。因为树的形态是随机的，它的高为$\sqrt{n}$n​ 的级别。那么需要一个 $O(nh)$O(nh) 的算法。

但我只会 $O(n(! \times n)$O(n(!×n) 的暴力，溜了。