企业官网建设流程全解析

如果你第一次在 UVa 12653 Buses 这道题上停下目光，多半是被范围吓住的：N 可以到 10^15，一个超过一千万亿的数字。我当时是在刷矩阵快速幂专题时碰到它的，第一反应是题目出错了——数座位而已，怎么数出个天文数字？后来把递推式列出来才想通，这道题本身就是为"线性递推 × 超大范围"量身定做的经典题：小范围用 DP，大范围用矩阵快速幂，两者正好在一道题里打通。这篇文章会从题意拆解开始，一步步给出递推式的来历、可以直接提交的 C++ 代码，最后聊聊我在 WSL2 里刷 UVa 时遇到的 "is not available" 网络问题。无论你是矩阵快速幂新手，还是只想要一份能跑的模板，应该都能从里面捞到东西。

1. 题意拆解：一排座位能产生多少种状态

1.1 题目在问什么

UVa 12653 的题干很短，说的是：一辆巴士有一排座位，编号从 1 到 N，N 最大可以到 10^15。每个座位有三种可能的状态：

• 空着，不坐人；
• 坐一个单独的乘客；
• 作为"双人座"的半边，和旁边一个座位一起坐两位结伴出行的乘客。

注意第三个状态有硬性要求：两个座位必须相邻，且一旦组成双人座，这两个座位就被这一对乘客占死了，不能再拆开坐两个单独的人。一辆完整巴士的状态，就是这 N 个座位在以上规则下形成的一个"全排安排"。题目要求输出所有合法安排的数量，结果对 1,000,000,007 取模。输入是多组数据，一直读到文件末尾。

我第一次读题时卡在了一个地方：两个相邻座位各自坐一个单独乘客，和这两个座位组成一个双人座坐两位结伴乘客，算不算两种方案？答案是算。前者座位层面是两个"单人座"，后者是一个"双人座"，状态描述完全不同，所以计数时都要分别算进去。这个细节直接决定递推式里那个 2 是从哪来的。

1.2 手推递推式：从"最右边发生了什么"开始

这种序列计数题，最顺手的突破口是看序列的最右边。假设我已经知道了 n 个座位之前所有长度的方案数，现在想知道 dp[n]，只需要关心最后一个座位到底处于哪种状态。

• 情况 A：第 n 个座位空着。它不影响前面的座位，前面的 n-1 个座位随便怎么安排都行，贡献 dp[n-1] 种。
• 情况 B：第 n 个座位坐着一个单独乘客。前面的 n-1 个座位依然是独立问题，贡献同样 dp[n-1] 种。
• 情况 C：第 n 个座位是某个双人座的半边。因为双人座必须占两个相邻座位，所以它只能和第 n-1 个座位组成一对，这两个座位被这一对乘客占死；剩下的 n-2 个座位又变回独立问题，贡献 dp[n-2] 种。

把三个情况加起来，递推式就出来了：

dp[n] = 2 × dp[n-1] + dp[n-2]

这个式子长得有点像斐波那契，但前面多了个 2。原因就是最后一位要么空、要么单人，两种情况都完全不影响更左边的内容，所以系数是 2；只有"成为双人座半边"这种可能必须把倒数第二位一起绑定。

1.3 边界初值：dp[0] 和 dp[1] 不能拍脑袋

有递推式还得有初值。dp[0] 表示一辆有 0 个座位的车，唯一合法状态就是"什么都没有"，所以 dp[0] = 1。dp[1] 表示一个座位，它不能组成双人座，只能空着或坐一个人，所以 dp[1] = 2。

验证一下：dp[2] = 2×2+1 = 5。手工枚举 2 个座位，状态分别是：全空、第 1 个单人、第 2 个单人、两个都单人、两个组成双人座，正好 5 种。dp[3] = 2×5+2 = 12，你也可以闲着没事手推出这 12 种，能把递推式的意义彻底吃透。这里有一个被很多人忽略的点：空座位不是"没有状态"，它和单人座一样是一种需要计数的可见安排。很多人初写这道题会把 dp[0] 顺手写成 0，然后前几项就对不上，最后只能对着题解改数字，却不知道为什么。

2. 为什么必须上矩阵快速幂：从 O(N) 到 O(log N)

2.1 线性递推的另一种写法

如果 N 只有几千，上面的 DP 数组或者两个滚动变量就能跑完，复杂度 O(N) 完全没问题。可这里是 10^15，就算用滚动变量，也要执行 10^15 次取模，在普通 OJ 上基本等于跑不完。这时候需要把"逐项算"升级成"跳着算"。

办法是把递推关系写成一个矩阵乘法。把相邻两个 dp 值放在同一个列向量里：

[dp[n] ] [dp[n-1]]

它和上一个状态的关系是：

[dp[n] ] [2 1] [dp[n-1]] [dp[n-1]] = [1 0] × [dp[n-2]]

只要验证一下矩阵乘法的第一行：2×dp[n-1] + 1×dp[n-2]，正好就是递推式；第二行是 dp[n-1] 原样保留。所以矩阵 T = [[2,1],[1,0]] 完全等价于原递推式。

于是求 dp[n] 就变成了求 T 的 n 次方：T^n 的第一行第一列恰好就是 dp[n]。为什么？因为 T^1 第一行第一列是 2 对应 dp[1]，T^2 第一行第一列是 5 对应 dp[2]，数学归纳一下就对上了。有读者可能觉得"矩阵乘法能当递推用"很魔法，但本质就是我们把两个递推变量打包，让矩阵负责同时更新它们。

2.2 快速幂：二进制拆分省时间

直接算 T^n 要乘 n 次，还是 O(N)。快速幂的思路是：把 n 写成二进制，例如 n = 19 = 10011₂，于是 T^19 = T^16 × T^2 × T^1。我们不需要真的从 1 乘到 19，只需要不断把矩阵自乘，得到 T^1, T^2, T^4, T^8, T^16，再把二进制位上是 1 的那些挑出来相乘。自乘的次数是 log₂(n) 左右，每次乘 2×2 矩阵的代价是 8 次乘法加若干次加法取模。

所以总复杂度从 O(N) 掉到了 O(log N)。10^15 的二进制大约 50 位，循环次数不超过 50 次，这在 OJ 上就是瞬时完成的事。很多初学者把"矩阵快速幂"当成一个需要背诵的模板，其实只要记住两个关键点：一个是矩阵怎么构造，一个是快速幂为什么能把指数拆分。这两点想通了，模板可以现场推。

这里再补一句：取模可以在乘法过程中做，也可以最后做。业界惯例是每次乘法取模，因为矩阵里的数很快就会超过 long long 能表示的范围。这道题的模数是 1e9+7，两个这样的数相乘接近 1e18，刚好在 long long 范围内，但如果不及时取模，再来几次连乘就溢出了。

3. 可直接提交的 C++ 实现与逐行解读

3.1 完整代码

直接贴一份 C++17 可以提交的代码，UVa 的 G++ 也支持，后面逐块解释。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007LL; struct Mat { ll a[2][2]; Mat(bool identity = false) { memset(a, 0, sizeof(a)); if (identity) { a[0][0] = a[1][1] = 1; } } }; Mat mul(const Mat& A, const Mat& B) { Mat C; for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 2; ++k) C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD; return C; } Mat power(Mat base, ll exp) { Mat res(true); while (exp > 0) { if (exp & 1) res = mul(res, base); base = mul(base, base); exp >>= 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; while (cin >> n) { Mat T; T.a[0][0] = 2; T.a[0][1] = 1; T.a[1][0] = 1; T.a[1][1] = 0; Mat ans = power(T, n); cout << ans.a[0][0] << '\n'; } return 0; }

3.2 代码里容易被忽略的细节

第一个细节是Mat(bool identity = false)这个构造函数。C++ 里结构体如果带默认参数构造函数，Mat T;和Mat res(true);都会正确初始化。没有这个构造函数的版本，可能随机读到栈上残留的数据，本地偶尔跑对、OJ 上 WA 到怀疑人生，其实就是没清零。

第二个细节是while (cin >> n)。UVa 很多老题目都是多组测试数据直到 EOF，有时候输入最后还会跟一个空行，用cin >> n可以自动跳过空白字符，不需要特殊处理。千万别写成只读一个 n 就跑，样例过了也照样 WA。

第三个细节是幂次 n 直接传给power(T, n)。前面说过 T^n 的第一行第一列就是 dp[n]，包括 n = 0 时 T^0 是单位矩阵，输出 1，对应空车一种方案，逻辑上是闭环的。

关于乘法顺序：res = mul(res, base)这里不能写反，因为矩阵乘法不满足交换律。虽然这道题的矩阵有点特殊，乘以它自己或者单位矩阵时顺序不敏感，但养成"res × base"的习惯以后做更复杂的矩阵快速幂才不会翻车。

4. 从本地对拍到 AC：怎么验证这道题写对了

4.1 暴力递推做交叉验证

矩阵快速幂最大的隐患是"写错矩阵但样例恰好对"。为了不带着错误代码去 OJ 试错，本地一定要准备一个暴力版本。由于这道题的递推式简单，暴力版本用两个滚动变量就行：

ll brute(ll n) { if (n == 0) return 1; if (n == 1) return 2; ll a = 1, b = 2; for (ll i = 2; i <= n; ++i) { ll c = (2 * b + a) % MOD; a = b; b = c; } return b; }

然后在 main 里循环 n 从 0 到 100，同时调用 brute(n) 和 power(T, n).a[0][0]，只要出现不一致就立刻输出 n 停止。我刷题时的习惯是：任何用矩阵快速幂的题都先随机对拍 1000 组再提交，小数据上矩阵和暴力答案一致，心里才有底。

for (ll n = 0; n <= 100; ++n) { Mat T; T.a[0][0] = 2; T.a[0][1] = 1; T.a[1][0] = 1; T.a[1][1] = 0; ll fast = power(T, n).a[0][0]; ll slow = brute(n); if (fast != slow) { printf("Mismatch at n=%lld: fast=%lld slow=%lld\n", n, fast, slow); return 1; } }

4.2 几个值得手测的边界

除了随机对拍，固定测几个边界也能快速定位问题：

• n = 0 输出 1；
• n = 1 输出 2；
• n = 2 输出 5；
• n = 3 输出 12；
• n = 10 输出 5741。

这几个值任何一个不对，说明递推矩阵构造或初值处理有问题。如果 n 比较大的话，直接看取模结果是否在 [0, MOD-1] 区间内，如果输出了负数或者大于 1e9+7 的数，多半是中间变量溢出或者用了 int 做乘法。

还有一个输入输出的坑：UVa 的输出通常不要求带 "Case #x" 之类的前缀，直接每行一个数字。这一点和很多其他 OJ 风格不同，提交前看一眼题目里的 Sample Output 是最稳的。以前我就吃过亏，把别的 OJ 的习惯带过来，结果输出格式错被 WA 了一次。

5. WSL2 里刷 UVa 的 "is not available" 排查手记

5.1 两种常见报错场景

我在 WSL2（Windows Subsystem for Linux 2）环境下刷题时，遇到过和 "uva is not available" 相关的两类问题。第一类是命令行工具访问 UVa 网站超时，curl 直接报连接失败；第二类是在 WSL2 的 Ubuntu 里执行某个安装命令时，包管理器提示 Package uva is not available。后者通常是软件源里没有这个名字的包，或者包名拼错了——UVa 的评测本身是网页端流程，本地并不需要专门装一个客户端，所以看到这种提示别硬刚，换个思路用网页提交就行。

真正影响刷题的是第一类。我踩过最典型的一次：Windows 宿主机浏览器打开 UVa 题目页一切正常，WSL2 里 curl 却永远卡住，页面一直显示 is not available。这种"宿主机通、虚拟机不通"的情况，多半是 WSL2 自己的网络问题，不是题目那边挂了。

5.2 分步排查：DNS、MTU、重启三件套

我的排查顺序固定是下面这几步，每一步都能解决相当一部分问题。

第一步看 DNS。执行cat /etc/resolv.conf，WSL2 默认 NAT 模式下，nameserver 经常指向虚拟网卡上的网关地址，这个地址在某些网络环境下并不好用。如果发现解析异常，先简单粗暴地把 DNS 换成公共 DNS，比如 114.114.114.114 或 1.1.1.1。注意 WSL2 重启后 /etc/resolv.conf 会被自动覆盖，想保留修改，需要在 /etc/wsl.conf 里写入[network]设置并关闭generateResolvConf，再去手动改文件。

第二步查 MTU。WSL2 的虚拟网卡有时会继承宿主机的 MTU 1500，但中间多了一层 NAT 转发，大包容易被丢，表现就是 ping 小包能通、curl 大流量卡死。临时把网卡 MTU 调小可以快速验证：sudo ifconfig eth0 mtu 1400，如果之后 curl 正常了，就把这条命令加到启动脚本里。

第三步是重启 WSL。在 Windows 管理员 PowerShell 里执行wsl --shutdown，然后重新进入 WSL2。这个操作会把虚拟网卡、DNS 缓存、之前的网络状态全部重置，很多"半通不通"的玄学问题，重启一次就好了。

5.3 网站本身挂了怎么办

如果上面三步都试完，curl 还是报 is not available，那就要考虑到另一种可能：UVa 那台老服务器自己又 down 了。UVa 的服务器稳定性在算法竞赛圈子里是出了名的看心情，评测高峰期或机房小故障都能导致页面不可达。这种时候没必要跟服务器硬耗，可以直接用支持 UVa 题目的虚拟判题平台来提交，或者干脆离线自测。

我个人的习惯是：把样例和随机构造的输入全部离线跑过，再用暴力对拍确认结果，最后等网站恢复正常再去提交一次。对题目本身的学习目的来说，本地验证和 UVa 提交通过的效果是一样的；对提交这件事来说，换个时间段访问常常就好了。