解题思路

题意要求：一段长度为 $n$ 的模式序列（字母表为 $\{1,\dots,9\}$），在“至多一次相邻交换”下得到的所有序列都必须没有相邻的两个 1（否则称为故障）。我们要统计这样的序列个数并对 $10^9+7$ 取模。

关键等价化 把除 1 以外的数字都看作同一种“非 1”（记作 $X$），但每个 $X$ 实际有 8 种取值。于是序列仅与“1 / 非1”的形态有关，最后再用 $8^{\text{非1个数}}$ 加权即可。

考虑一次相邻交换对是否出现“11”的影响。交换位置 $i$ 与 $i+1$ 的元素，仅可能新产生在三对相邻位置上的“11”：$(i-1,i)$、$(i,i+1)$、$(i+1,i+2)$。其中

• 中间对 $(i,i+1)$ 若交换后为 “11”，则交换前相邻两位本来就是 “11”，与“原序列正常”矛盾，故不可能新产生；
• 两侧对会在且仅在出现形态 1 X 1（即距离为 2 的两个 1）时被交换拉到一起，从而形成“11”。

再结合“原序列也要正常（无相邻 1）”，得到充要条件：

可靠序列 $\iff$ 序列中任意两个 1 的下标距离 至少为 3（既不允许相邻“11”，也不允许“1 X 1”）。

于是问题化为：在长度为 $n$ 的序列中放若干个 1，使任意两个 1 的距离至少为 3；其余位置放 $X$（每个位置有 8 种取值）。

线性递推 设 $f(n)$ 为答案。讨论首位：

• 若首位为 $X$：有 8 种选择，剩余 $n-1$ 位可为任意可靠序列，贡献 $8\,f(n-1)$；
• 若首位为 1：则第 2、3 位必须是 $X$（各 8 种），之后从第 4 位开始是一个长度为 $n-3$ 的任意可靠序列，贡献 $8^2\,f(n-3)=64\,f(n-3)$。

得到递推：

$$f(n)=8\,f(n-1)+64\,f(n-3),\quad n\ge 3$$

初值：

$$f(0)=1\ \ (\text{空序列}),\quad f(1)=9\ (1\text{ 或 }X),\quad f(2)=9^2-1=80\ (\text{仅排除 }11). $$

复杂度分析

• 时间复杂度：$O(n)$（一次线性递推）。
• 空间复杂度：$O(1)$（仅用常数个滚动变量）。

代码实现

Python

import sys

MOD = 1000000007

# 计算长度为 n 的可靠信号灯序列数量
def solve(n: int) -> int:
    if n == 0:
        return 1
    if n == 1:
        return 9
    if n == 2:
        return 80
    # 滚动变量：a=f(0), b=f(1), c=f(2)
    a, b, c = 1, 9, 80
    for i in range(3, n + 1):
        # f(i) = 8*f(i-1) + 64*f(i-3)
        d = (8 * c + 64 * a) % MOD
        a, b, c = b, c, d
    return c

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    print(solve(n) % MOD)

if __name__ == "__main__":
    main()

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static final long MOD = 1000000007L;

    // 计算长度为 n 的可靠信号灯序列数量
    static long solve(int n) {
        if (n == 0) return 1L;
        if (n == 1) return 9L;
        if (n == 2) return 80L;
        long a = 1L;  // f(0)
        long b = 9L;  // f(1)
        long c = 80L; // f(2)
        for (int i = 3; i <= n; i++) {
            // f(i) = 8*f(i-1) + 64*f(i-3)
            long d = (8L * c + 64L * a) % MOD;
            a = b;
            b = c;
            c = d;
        }
        return c % MOD;
    }

    public static void main(String[] args) throws IOException {
        // 简洁输入：一行一个整数 n
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine().trim();
        int n = Integer.parseInt(line);
        System.out.println(solve(n));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

// 计算长度为 n 的可靠信号灯序列数量
long long solve(int n) {
    if (n == 0) return 1LL;
    if (n == 1) return 9LL;
    if (n == 2) return 80LL;
    long long a = 1;   // f(0)
    long long b = 9;   // f(1)
    long long c = 80;  // f(2)
    for (int i = 3; i <= n; ++i) {
        // f(i) = 8*f(i-1) + 64*f(i-3)
        long long d = (8LL * c + 64LL * a) % MOD;
        a = b;
        b = c;
        c = d;
    }
    return c % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    cout << solve(n) << "\n";
    return 0;
}

题目内容

某交通枢纽采用智能信号灯系统，该系统支持九种模式，用编号 $1$ ~ $9$ 来表示。信号灯会按时间顺序输出一段长度为 $n$ 的模式序列(例如:$137632...$)。

系统有严格的安全约束:若序列中存在两个相邻的 $1$ 号模式，会触发设备故障，称为“故障序列”;反之，无相邻 $1$ 号模式的序列称为“正常序列”。例如:$124、2418、1$ 是正常序列;$11、8111、61192$ 是故障序列。

由于硬件特性，信号灯在切换模式时至多会出现一次“相邻模式交换”的误差(例如序列 $123$ 可能变成 $132$ )。若一段序列在“至多交换一次相邻模式”的条件下，得到的所有结果均为正常序列，则称其为“可靠信号灯序列”;若交换后可能得到故障序列，则称其为“不可靠信号灯序列”。例如:$124、1、123123$ 是可靠信号灯序列;$24141、1214、311$ 是不可靠信号灯序列。请计算有多少种不同的长度为n的可靠信号灯序列，结果对 $1000000007$ 取模。

输入描述

输入一行，包含一个整数 $n$ ，其中 $1≤n≤100000$，表示信号灯序列的长度。

输出描述

输出一行，包含一个整数，表示长度为 $n$ 的可靠信号灯序列的种类数。答案对 $1000000007$ 取模。

样例1

输入

2

输出

80

说明

长度为 $2$ 的信号灯序列共有 $9^2-81$ 种，其中 $11$ 为不可靠信号灯序列，$81-1=80$ 。

样例2

输入

3

输出

704