洛谷P2233 [HNOI2002]公交车路线 题解

题目链接：P2233 [HNOI2002]公交车路线

题意：

在幻想郷新建的环城公路上一共有 \(8\) 个公交站，分别为 A、B、C、D、E、F、G、H。

公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站 \(A\) 到公交站 \(D\)，你就至少需要换 \(3\) 次车。

不过琪露诺的方向感极其糟糕，我们知道从公交站 \(A\) 到公交 \(E\) 只需要换 \(4\) 次车就可以到达，而她却总共换了 \(n\) 次车！

注意琪露诺一旦到达公交站 \(E\)，她不会笨到再去换车。现在希望你计算一下琪露诺有多少种可能的乘车方案。

输入格式：

仅有一个正整数 \(n\)，表示琪露诺从公交车站 A 到公交车站 E 共换了 \(n\) 次车。

输出格式：

输出一个正整数表示方案数，由于方案数很大，请输出方案数除以 \(1000\) 后的余数。

数据范围：

\(4\le n\le10^7\)。

首先从 \(E\) 断环为链，因为走到 \(E\) 以后不会再换车。

此时的公交线路就关于 \(A\) 对称了，容易发现相对称的两个站点方案数是相同的。

故我们只对 \(A \sim D\) 做一遍dp。设 \(f_{i,j}\) 表示走了 \(i\) 步到 \(j\) 的方案数，则有 \[ f_{i,j} = f_{i-1,j-1} + f_{i-1,j+1} \] 稍微滚滚数组就好啦，时间复杂度 \(\mathcal{O}(n)\) ，代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
const int mod = 1000;
#define N ((int)())

int n,p,f[2][4];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; p = 1; f[0][0] = 1;
    for(int k = 1; k < n; k++, p ^= 1)
    {
        f[p][0] = 2 * f[p ^ 1][1] % mod;
        f[p][1] = (f[p ^ 1][0] + f[p ^ 1][2]) % mod;
        f[p][2] = (f[p ^ 1][1] + f[p ^ 1][3]) % mod;
        f[p][3] = f[p ^ 1][2] % mod;
    }
    cout << 2 * f[p ^ 1][3] % mod << '\n';
    return 0;
}