洛谷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;
}