【MX-S4-T4】「yyOI R2」youyou 的三进制数

原题链接：[https://oier.team/problems/88](https://oier.team/problems/88)

现在有 $0 \sim n$ 共 $n + 1$ 个数。 定义 $(x)_{3}$ 表示十进制数 $x$ 的三进制形式。**如果没有特别强调，那么这些数均为十进制形式。** youyou 想构造一个序列长度为 $p$（$p \ge 1$）的非负整数序列 $a$。使之满足： - $a_i \in [0,n]$。 - 不存在 $i,j$（$1 \le i <j \le p$），使得 $a_i = a_j$。 - 对于任意 $1 \le i < n$，$a_i$ 与 $a_{i+1}$ 至少满足以下四个条件中的一个： 1. $(a_i)_3$ 去掉最后一位，恰好等于 $(a_{i+1})_3$（若只有一位，则去掉后的数字为 $0$）。 2. 在 $(a_i)_3$ 末尾添上某一位 $t(0 \le t \le 2)$，恰好等于 $(a_{i+1})_3$（若 $a_i = 0$，则添加后舍去前置 $0$）。 3. $a_i \le w$， $(a_i)_3$ 的末尾不是 $0$，且将末尾的一位数字移到开头与 $(a_{i + 1})_3$ 相等。 4. 当 $(a_i)_3$ 长度 $\ge 2$，且 $(a_i)_3$ 次高位非零时，将 $(a_i)_3$ 开头的一位数字移到末尾，形成的数的十进制值 $\le w$，且恰好等于 $(a_{i+1})_3$。 这样的序列 $a$ 被称为“完美的”。 youyou 认为，如果十进制三元组 $(x,y,z)$ 是好的，必须满足以下条件： - $0 \le x,y,z \le n$，$x \neq y$。 - 存在至少一个”完美的“序列 $b$，使得十进制下有 $b_1=x$，$b_s = y$。其中 $s$ 为序列长度。 - 存在至少一个”完美的”序列 $c$，使得十进制下有 $c_1=z$。同时，对于上述**任意的** $b$，均有**恰好**一对 $(i, j)$，满足 $1 \le i \le |b|$，$1 \le j \le |c|$，使得 $b_i = c_j$。 对于每一个 $0 \le z \le n$，求能构成“好的”三元组 $(x,y,z)$ 的有序对 $(x,y)$ 的个数。

仅一行，为一个正整数 $n$ 和一个非负整数 $w$，其含义在题目描述中给出。

共 $n + 1$ 行，其中第 $i + 1$ 行一个数表示当 $z = i$ 时，能构成“好的”三元组 $(x,y,z)$ 的有序对 $(x,y)$ 的个数。

4 3

20
20
20
20
20

**【样例解释 #1】** 一共有 $5$ 个数，用三进制表示分别为 $0,1,2,10,11$。 当 $z = 0,1,2,3,4$ 时，全部 $(x,y)(x \neq y)$ 数对均满足题意。 下面给出三元组 $(2,3,1)$ 是“好的”的证明。 当 $x=2,y=3,z=1$ 时，序列 $b$ 可以为 $\{2,0,1,3\}$。 其中 $b_1,b_2$ 满足条件 $1$，$b_2,b_3$ 满足条件 $2$，$b_3,b_4$ 满足条件 $2$。 可以证明只有这一个序列 $b$ 满足题意。因此，存在 $c = \{1\}$，使得 $B \cap C = \{1\}$。所以 $(2,3,1)$ 是“好的”三元组。 **【样例 #2】** 见附件中的 ```ternary/ternary2.in``` 与 ```ternary/ternary2.ans```。 该组样例满足测试点 $4\sim 6$ 的约束条件。 **【样例 #3】** 见附件中的 ```ternary/ternary3.in``` 与 ```ternary/ternary3.ans```。 该组样例满足测试点 $7\sim 10$ 的约束条件。 **【样例 #4】** 见附件中的 ```ternary/ternary4.in``` 与 ```ternary/ternary4.ans```。 该组样例满足测试点 $13\sim 15$ 的约束条件。 **【样例 #5】** 见附件中的 ```ternary/ternary5.in``` 与 ```ternary/ternary5.ans```。 该组样例满足测试点 $20\sim 25$ 的约束条件。 **【数据范围】** 本题共 $25$ 个测试点，每个 $4$ 分。 | 测试点编号 | $n$ | $w$ | 特殊性质 | :-----------: | :-----------: | :-----------: | :-----------: | | $1 \sim 3$ | $\le 18$ | $\le 18$ | 无 | $4 \sim 6$ | $\le 242$ | $\le 242$ | 无 | $7 \sim 10$ | $\le 6560$ | $\le6560$ | 无 | $11\sim12$ | $\le 10^5$ | $\le 10^5$ | 无 | $13\sim15$ | $\le 3 \times 10^5$ | $\le 10^5$ | 有 | | $16\sim 17$ | $\le 3 \times 10^5$ | $=0$ | 无 | | $18\sim 19$ | $\le 3 \times 10^5$ | $=n$ | 无 | | $20\sim25$ | $\le 3 \times 10^5$ | $\le 3 \times 10^5$ | 无 | 特殊性质：$w \ge 10^4$。 对于全部数据，保证：$1\le n \le 3 \times 10^5$，$0 \le w \le n$。