（P15440）众所周知提交答案题的正解是

· · 题解

众所周知此题的正解是找到 @tuntunQwQ 巨佬向祂抄一份答案，然后输出 125793683，交一发AC了，然后此题就做完了。

当然你也可以靠 wrong answer On line <L> column <C>, read <x>, expected <y>. 的方式看调试信息交九发AC。

好了讲正解。

注意到信号灯个数为 2025，考虑时间复杂度小于 O(n^2) 的DP。

为了方便，我们将全部的灯的状态设为「第 i 次操作后亮的灯的数量 - 初始亮的灯的数量」。显然第一次操作后灯的状态为 0。同时我们设 dp_{i,j} 表示第 (i+1) 次操作后（这里注意设计的状态）状态为 j 的方案数。

题目要求亮灯数量恰好有三种不同值，那么我们的状态集合需要是一个元素不可重复的三元组。注意到第 i+1 次操作和第 i 次操作相比仅改变了第 i 盏灯的状态，所以全部的灯的状态只有可能 +1 （灭变亮）或 -1 （亮变灭）。于是我们得到如下两条：

综合以上两条，我们只需要在 [0,2],[-1,1],[-2,0] 三种值域上跑 DP，把得到的方案数相加就可以了。

然后呢？

Wrong Answer.wrong answer On line 1 column 9, read 7, expected 3.

多的 4 在哪里呢？我们又看到了“恰好”，“元素不可重复”这些字眼，然后我们就想到我们需要把只有两个元素的状态集合去掉了。那么我们就在 [0,1],[-1,0] 这两种值域上跑 DP，把这两种情况得到的方案数去掉就可以了。注意要去两遍，因为 [0,1] 在 [0,2],[-1,1] 中各出现了一遍，[-1,0] 在 [-1,1],[-2,0] 各出现了一遍。

时间复杂度 O(n)。

::::success[c++ code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,P=1e9+7;
int n=2025;
int f[N][3],ans;
signed main(){
    //跑[0,2]上的DP
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=f[i][2]=f[i-1][1];
        f[i][1]=(f[i-1][0]+f[i-1][2])%P;
    }
    ans=(ans+f[n][0]+f[n][1]+f[n][2])%P;
    //跑[-1,1]上的DP
    memset(f,0,sizeof f);
    f[0][1]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=f[i][2]=f[i-1][1];
        f[i][1]=(f[i-1][0]+f[i-1][2])%P;
    }
    ans=(ans+f[n][0]+f[n][1]+f[n][2])%P;
    //跑[-2,0]上的DP
    memset(f,0,sizeof f);
    f[0][2]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=f[i][2]=f[i-1][1];
        f[i][1]=(f[i-1][0]+f[i-1][2])%P;
    }
    ans=(ans+f[n][0]+f[n][1]+f[n][2])%P;
    //跑[-1,0]上的DP
    memset(f,0,sizeof f);
    f[0][1]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=f[i-1][1];
        f[i][1]=f[i-1][0];
    }
    ans=(ans-2*(f[n][0]+f[n][1])+P)%P;
    //跑[0,1]上的DP
    memset(f,0,sizeof f);
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][0]=f[i-1][1];
        f[i][1]=f[i-1][0];
    }
    ans=(ans-2*(f[n][0]+f[n][1])+P)%P;
    //输出
    cout<<ans<<'\n';
    return 0;
}

::::

Python 代码由 AI 改写，经人工核查与 c++ 代码思路与实现完全一致。 ::::success[python code]

def main():
    n = 2025
    P = 10**9 + 7
    ans = 0
    # 1. 跑[0,2]上的DP
    f = [[0] * 3 for _ in range(n + 1)]
    f[0][0] = 1
    for i in range(1, n + 1):
        f[i][0] = f[i-1][1] % P
        f[i][2] = f[i-1][1] % P
        f[i][1] = (f[i-1][0] + f[i-1][2]) % P
    sum_val = (f[n][0] + f[n][1] + f[n][2]) % P
    ans = (ans + sum_val) % P
    # 2. 跑[-1,1]上的DP
    f = [[0] * 3 for _ in range(n + 1)]
    f[0][1] = 1
    for i in range(1, n + 1):
        f[i][0] = f[i-1][1] % P
        f[i][2] = f[i-1][1] % P
        f[i][1] = (f[i-1][0] + f[i-1][2]) % P
    sum_val = (f[n][0] + f[n][1] + f[n][2]) % P
    ans = (ans + sum_val) % P
    # 3. 跑[-2,0]上的DP
    f = [[0] * 3 for _ in range(n + 1)]
    f[0][2] = 1
    for i in range(1, n + 1):
        f[i][0] = f[i-1][1] % P
        f[i][2] = f[i-1][1] % P
        f[i][1] = (f[i-1][0] + f[i-1][2]) % P
    sum_val = (f[n][0] + f[n][1] + f[n][2]) % P
    ans = (ans + sum_val) % P
    # 4. 跑[-1,0]上的DP
    f = [[0] * 3 for _ in range(n + 1)]
    f[0][1] = 1
    for i in range(1, n + 1):
        f[i][0] = f[i-1][1] % P
        f[i][1] = f[i-1][0] % P
    sum_val = (f[n][0] + f[n][1]) % P
    ans = (ans - 2 * sum_val + P) % P  # 加P避免负数
    # 5. 跑[0,1]上的DP
    f = [[0] * 3 for _ in range(n + 1)]
    f[0][0] = 1
    for i in range(1, n + 1):
        f[i][0] = f[i-1][1] % P
        f[i][1] = f[i-1][0] % P
    sum_val = (f[n][0] + f[n][1]) % P
    ans = (ans - 2 * sum_val + P) % P

    # 输出结果
    print(ans)

if __name__ == "__main__":
    main()

::::