P11220 [MX-S4-T4] "yyOI R2" youyou's Ternary Numbers

Original link: 。

There are $n + 1$ numbers from $0$ to $n$. Let $(x)_{3}$ denote the ternary representation of the decimal number $x$. **Unless explicitly stated otherwise, all numbers are in decimal form.** youyou wants to construct a non-negative integer sequence $a$ of length $p$ ($p \ge 1$), such that: - $a_i \in [0,n]$。 - There do not exist $i,j$ ($1 \le i < j \le p$) such that $a_i = a_j$。 - For any $1 \le i < n$, $a_i$ and $a_{i+1}$ satisfy at least one of the following four conditions: 1. Remove the last digit of $(a_i)_3$, and it becomes exactly $(a_{i+1})_3$ (if there is only one digit, then after removing it the number becomes $0$)。 2. Append a digit $t(0 \le t \le 2)$ to the end of $(a_i)_3$, and it becomes exactly $(a_{i+1})_3$ (if $a_i = 0$, then after appending, leading $0$ is discarded)。 3. $a_i \le w$, the last digit of $(a_i)_3$ is not $0$, and moving the last digit to the front makes it equal to $(a_{i + 1})_3$。 4. When the length of $(a_i)_3$ is $\ge 2$ and the second highest digit of $(a_i)_3$ is non-zero, move the first digit of $(a_i)_3$ to the end; the decimal value of the resulting number is $\le w$, and it is exactly equal to $(a_{i+1})_3$。 Such a sequence $a$ is called "perfect". youyou believes that a decimal triple $(x,y,z)$ is good if and only if it satisfies all of the following conditions: - $0 \le x,y,z \le n$, and $x \neq y$。 - There exists at least one "perfect" sequence $b$ such that in decimal we have $b_1 = x$ and $b_s = y$, where $s$ is the length of the sequence。 - There exists at least one "perfect" sequence $c$ such that in decimal we have $c_1 = z$. At the same time, for **any** $b$ mentioned above, there is **exactly** one pair $(i, j)$ satisfying $1 \le i \le |b|$ and $1 \le j \le |c|$ such that $b_i = c_j$。 For each $0 \le z \le n$, find the number of ordered pairs $(x,y)$ that can form a good triple $(x,y,z)$.

One line containing a positive integer $n$ and a non-negative integer $w$, whose meanings are given in the statement.

Output $n + 1$ lines. The $(i + 1)$-th line contains one number, indicating that when $z = i$, the number of ordered pairs $(x,y)$ that can form a good triple $(x,y,z)$.

**[Sample Explanation #1]** There are $5$ numbers, whose ternary representations are $0,1,2,10,11$ respectively. When $z = 0,1,2,3,4$, all pairs $(x,y)$ with $x \neq y$ satisfy the requirement. Below is a proof that the triple $(2,3,1)$ is good. When $x = 2, y = 3, z = 1$, the sequence $b$ can be $\{2,0,1,3\}$. Here, $b_1,b_2$ satisfy condition $1$, $b_2,b_3$ satisfy condition $2$, and $b_3,b_4$ satisfy condition $2$. It can be proved that only this sequence $b$ satisfies the requirement. Therefore, there exists $c = \{1\}$ such that $B \cap C = \{1\}$. Hence $(2,3,1)$ is a good triple. **[Sample #2]** See ```ternary/ternary2.in``` and ```ternary/ternary2.ans``` in the attachment. This sample satisfies the constraints of test points $4 \sim 6$. **[Sample #3]** See ```ternary/ternary3.in``` and ```ternary/ternary3.ans``` in the attachment. This sample satisfies the constraints of test points $7 \sim 10$. **[Sample #4]** See ```ternary/ternary4.in``` and ```ternary/ternary4.ans``` in the attachment. This sample satisfies the constraints of test points $13 \sim 15$. **[Sample #5]** See ```ternary/ternary5.in``` and ```ternary/ternary5.ans``` in the attachment. This sample satisfies the constraints of test points $20 \sim 25$. **[Constraints]** This problem has $25$ test points, $4$ points each. | Test Point ID | $n$ | $w$ | Special Property | | :-----------: | :-----------: | :-----------: | :-----------: | | $1 \sim 3$ | $\le 18$ | $\le 18$ | None | | $4 \sim 6$ | $\le 242$ | $\le 242$ | None | | $7 \sim 10$ | $\le 6560$ | $\le6560$ | None | | $11\sim12$ | $\le 10^5$ | $\le 10^5$ | None | | $13\sim15$ | $\le 3 \times 10^5$ | $\le 10^5$ | Yes | | $16\sim 17$ | $\le 3 \times 10^5$ | $=0$ | None | | $18\sim 19$ | $\le 3 \times 10^5$ | $=n$ | None | | $20\sim25$ | $\le 3 \times 10^5$ | $\le 3 \times 10^5$ | None | Special property: $w \ge 10^4$。 For all data, it is guaranteed that $1 \le n \le 3 \times 10^5$ and $0 \le w \le n$。 Translated by ChatGPT 5