新千题计划 11#：[CQOI 2018] 九连环

连环"/>

新千题计划 11#：[CQOI 2018] 九连环

九连环 n n n 连环是一个 n n n 长全 0 序列，求使其变成全 1 序列的最小操作次数。一次变换改一个数，可改第 i i i 个数当且仅当 i = 1 i = 1 i=1 或 i i i 是序列中第一个 1 所在位置。

递推。 该数列已被 A000975 - OEIS 收录。

欲解 n n n 连环，需要 1）解 n − 1 n - 1 n−1 连环，即 111 ⋯ 10 111 \cdots 10 111⋯10；2）将前 n − 2 n - 2 n−2 位的 1 视为 0，反向解 n − 2 n - 2 n−2 连环，即 000 ⋯ 010 000 \cdots 010 000⋯010；3）将末位变为 1，即 000 ⋯ 011 000 \cdots 011 000⋯011；4）解 n − 2 n - 2 n−2 连环。故递推式为 a n = a n − 1 + 2 a n − 2 + 1 a_n = a_{n - 1} + 2a_{n - 2} + 1 an​=an−1​+2an−2​+1，显然 a 1 = 1 , a 2 = 2 a_1 = 1, a_2 = 2 a1​=1,a2​=2。

我们用特征根法解通项公式。令 b n = a n + 1 2 b_n = a_n + \dfrac 1 2 bn​=an​+21​，则 b n = b n − 1 + 2 b n − 2 , b 1 = 3 2 , b 2 = 5 2 b_n = b_{n - 1} + 2b_{n - 2}, b_1 = \dfrac 3 2, b_2 = \dfrac 5 2 bn​=bn−1​+2bn−2​,b1​=23​,b2​=25​。其特征方程为 x 2 − x − 2 = 0 ⇒ x = − 1 or  2 x^2 - x - 2 = 0 \Rightarrow x = -1 \text{ or } 2 x2−x−2=0⇒x=−1 or 2，故通解为 b n = C 1 2 n + C 2 ( − 1 ) n b_n = C_1 2^n + C_2 (-1)^n bn​=C1​2n+C2​(−1)n，代入 b 1 , b 2 b_1, b_2 b1​,b2​ 有 C 1 = 2 3 , C 2 = − 1 6 C_1 = \dfrac 2 3, C_2 = -\dfrac 1 6 C1​=32​,C2​=−61​，故 b n = 2 n + 1 3 − ( − 1 ) n 6 , a n = 2 n + 1 3 − ( − 1 ) n 6 − 1 2 b_n = \dfrac {2 ^ {n + 1}} 3 - \dfrac {(-1)^n} 6, a_n = \dfrac {2 ^ {n + 1}} 3 - \dfrac {(-1)^n} 6 - \dfrac 1 2 bn​=32n+1​−6(−1)n​,an​=32n+1​−6(−1)n​−21​，容易改写成 ⌊ 2 3 ( 2 n − 1 ) ⌋ \lfloor \dfrac 2 3 (2^n - 1) \rfloor ⌊32​(2n−1)⌋。

高精咕了，以下是 Python 代码。

m = int(raw_input())
while m > 0:n = int(raw_input())print int(((2 ** (n + 1)) - 2) / 3)m = m - 1