如果你第一次在 UVa 12653 Buses 这道题上停下目光多半是被范围吓住的N 可以到 10^15一个超过一千万亿的数字。我当时是在刷矩阵快速幂专题时碰到它的第一反应是题目出错了——数座位而已怎么数出个天文数字后来把递推式列出来才想通这道题本身就是为线性递推 × 超大范围量身定做的经典题小范围用 DP大范围用矩阵快速幂两者正好在一道题里打通。这篇文章会从题意拆解开始一步步给出递推式的来历、可以直接提交的 C 代码最后聊聊我在 WSL2 里刷 UVa 时遇到的 is not available 网络问题。无论你是矩阵快速幂新手还是只想要一份能跑的模板应该都能从里面捞到东西。1. 题意拆解一排座位能产生多少种状态1.1 题目在问什么UVa 12653 的题干很短说的是一辆巴士有一排座位编号从 1 到 NN 最大可以到 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×21 5。手工枚举 2 个座位状态分别是全空、第 1 个单人、第 2 个单人、两个都单人、两个组成双人座正好 5 种。dp[3] 2×52 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 能表示的范围。这道题的模数是 1e97两个这样的数相乘接近 1e18刚好在 long long 范围内但如果不及时取模再来几次连乘就溢出了。3. 可直接提交的 C 实现与逐行解读3.1 完整代码直接贴一份 C17 可以提交的代码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 输出 1n 1 输出 2n 2 输出 5n 3 输出 12n 10 输出 5741。这几个值任何一个不对说明递推矩阵构造或初值处理有问题。如果 n 比较大的话直接看取模结果是否在 [0, MOD-1] 区间内如果输出了负数或者大于 1e97 的数多半是中间变量溢出或者用了 int 做乘法。还有一个输入输出的坑UVa 的输出通常不要求带 Case #x 之类的前缀直接每行一个数字。这一点和很多其他 OJ 风格不同提交前看一眼题目里的 Sample Output 是最稳的。以前我就吃过亏把别的 OJ 的习惯带过来结果输出格式错被 WA 了一次。5. WSL2 里刷 UVa 的 is not available 排查手记5.1 两种常见报错场景我在 WSL2Windows 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.confWSL2 默认 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 提交通过的效果是一样的对提交这件事来说换个时间段访问常常就好了。