1. 拿到题面的一瞬间管道取珠究竟想让你算什么1.1 操作规则与输出目标5月29日的每日一题是《管道取珠》我第一眼看到这个题面时脑子里直接冒出来一句话“这题难的地方根本不在取珠操作而在那个平方和。”先别急着看题我们把规则拆开它其实只说了三件事有两条管道第一条里面从上到下放着 n 颗珠子第二条里面从上到下放着 m 颗珠子。每轮你可以选择任意一条管道把管道口最外面的那颗珠子取出来。不断重复这个过程直到两条管道都取空。同一组珠子颜色序列可能会被多种不同的“取法顺序”造出来。假设某个颜色序列 S 一共有 f(S) 种取法能得到它题目最后让你求的是[\sum_{S} f(S)^2]规定结果对 1024523 取模。部分版本里会给出数据范围一般 n 和 m 都在几百的规模这种范围摆在那里基本就是在暗示千万不要把每一种颜色序列都真实枚举出来。这里有个容易误解的点很多新手会以为“取法顺序”只和选了哪条管道有关比如一条管道选1次、选2次、选3次……其实不是。颜色序列相同的两种取法中间可能经历过完全不同的管道选择顺序只是最终吐出来的颜色序列碰巧一样。比如黑白黑这个序列可以先从一号管取两个再从二号管取一个也可以先取一号的一个、二号的一个、再取一号的一个。只要最终颜色排列相同它们就都算 f(S) 的一份贡献。1.2 直接枚举的障碍在哪里假如不考虑平方我们只要统计“每种颜色序列的出现次数”这个题确实不难。因为它其实就是一个典型的二维取数 DP。设 g[i][j] 表示已经在一号管取了 i 颗、二号管取了 j 颗时能够得到多少种不同的颜色序列。转移也很好写当前这一颗从一号管取g[i][j] g[i-1][j]当前这一颗从二号管取g[i][j] g[i][j-1]。但问题来了g[i][j] 只是不同“取法路径”的数量不是不同“颜色序列”的数量。同一串颜色可能来自 g 里的很多路径而你最后要统计的不是路径数而是路径数的平方。这就像你在统计一个班级有多少人却突然要求你把“每个姓名出现的次数”平方后相加。只统计人数完全不够。有人会想那我给每个颜色序列开一个哈希表每走到一个序列就加一次计数最后再统一平方求和。理论上确实可行但实际不可能。因为可能的颜色序列数量最多能达到 2^(nm) 的数量级只要 n 和 m 稍微大一点哈希表直接炸穿。而且哈希碰撞、存储开销、枚举顺序都会变成新的麻烦。所以这道题真正的门槛是如何在不枚举颜色序列的前提下直接算出所有计数平方的总和。这正是“双重计数”思想最适合出场的地方。把每一条路径都当成一个人把两个人同时放上赛道问题就会换一副面孔。2. 核心转换把平方项看成“两个人一起取”2.1 f(S) 乘 f(S) 的另一种读法我们先忘记管道只盯着一个颜色序列 S。假设 f(S)3意思是有三条不同的取法路径都能得到 S。那 f(S)^29 代表什么别人可能会说“9 就是 3 的平方”但这句废话对解题没用。更有用的理解是从能生成 S 的三条路径里任选一条作为一号选手的路径再任选一条作为二号选手的路径两个选手的路径放在一起一共能组成 3×39 个有序路径对。注意是“有序”路径对一号选路径 A、二号选路径 B和一号选路径 B、二号选路径 A算两个不同的对子。这也是为什么用平方而不是用组合数平方天然地把先后顺序也算进去了。把每个颜色序列都做一次这个操作最终的答案就变成[ \sum_S f(S)^2 \sum_S (\text{能生成S的路径数}) \times (\text{能生成S的路径数}) ]右边这个式子可以重新组织成所有满足“两条路径生成同一个颜色序列”的有序路径对的总数。这样一来我们不再需要统计颜色序列 S 出现了多少次只需要去统计“成对”的路径。虽然路径对看起来比单条路径数量更多但它有一个巨大好处路径对能直接用 DP 状态来描述因为两条路径的每一步都能明确对应到一个坐标状态。2.2 双人同步取珠的模型现在引入一个很妙的重构把“一条取法路径”看成一个人在操作。原来只有一个人取珠现在改成两个人同时取珠。两个人各自维护一条管道组合但有两个前提两个人每一步都必须从自己的某条管道里取出一颗珠子。两个人当前这一步取出的珠子颜色必须相同。为什么必须相同因为最终只有两个人的完整输出序列完全相同才能对应到同一个颜色序列 S。如果他们某一步颜色不一样后面就算再同步也不可能再生成同一个 S 了。举个例子。假设最终目标颜色序列是“黑白黑”。一号选手的路径是一管黑、二管白、一管黑。二号选手的路径是二管白、一管黑、一管黑。两个人虽然在第一步分别从不同管道取珠但取出的颜色都是“黑”所以第一步就算匹配成功。第二步两人也都取出“白”第三步也都取出“黑”。三个步骤全部匹配成功于是这个路径对就该被计入答案。推广一下[ \sum_S f(S)^2 #{(P_1, P_2) \mid \text{路径}P_1\text{和路径}P_2\text{产生的颜色序列完全相同}} ]这个等式就是整道题的钥匙。每条单路径本身仍然对应着一组管道选择但我们现在不关心它吐出来的整个序列是什么了我们只关心两条路径在每条边是不是选了同样颜色的珠子。这个判断完全可以通过状态转移做到局部化不需要保存完整序列。用生活里的类比来说原来你是在统计“每个签文几个人抽到”现在你改成统计“两个人在同一时刻抽到一样签文的次数”。后者天然支持动态规划因为它只看当下这一步是否匹配。3. DP 状态设计四维坐标如何压成三维3.1 先写四维状态如果一点不压缩这道题的状态应该是四维的。因为双人路径要描述的东西很多一号选手已经在一号管取了 i 颗珠子一号选手已经在二号管取了 j 颗珠子二号选手已经在一号管取了 k 颗珠子二号选手已经在二号管取了 l 颗珠子。状态 dp[i][j][k][l] 表示在两个人都已经操作了若干次、并且到目前为止每一步颜色都匹配成功的情况下达到这种坐标组合的方案数。转移的时候每个人都面临两个选择从一号管取或者从二号管取。两个人合起来就有 2×24 种组合一号取一号管二号取一号管一号取一号管二号取二号管一号取二号管二号取一号管一号取二号管二号取二号管。每种组合都必须额外满足“两个人取出的珠子颜色相同”。这是四维 DP 最简单的写法逻辑非常清晰。问题是i、j、k、l 的取值范围都是几百四个维度相乘状态量爆炸根本跑不动。不过论坛里大部分题解都会告诉你这里存在一个隐藏等式可以砍掉一维。3.2 总操作数相等是压缩维度的关键一号选手操作的总步数是 ij二号选手操作的总步数是 kl。因为两个人是同步取珠的最终取完时总步数一定相等。更重要的是在 DP 的任何一个中间状态里如果我们要让两个选手仍然保持同步他们的总步数也必须一直相等。也就是说[ ij kl ]于是四个变量里只要知道任意三个第四个就能算出来。通常我们把双方的总步数记为 s把一号选手在一号管取的珠子数记为 i二号选手在一号管取的珠子数记为 j那么剩下两个量分别是一号选手在二号管已经取了 s-i 颗二号选手在二号管已经取了 s-j 颗。状态直接简化为 dp[s][i][j]。一维是总步数两维是双方各自消耗一号管珠子的数量看着是三维但因为 s 可以滚动本质上只需要维护二维数组。很多人一开始想不明白为什么 j 也是“一号管取了多少颗”而不是“二号管取了多少颗”。原因就在于我们选择了固定的参照物只看一号管的消耗进度。只要知道总步数和一号管消耗量二号管消耗量自然就是总数减去它。两边的信息其实是对称的选哪一维做参照都行只是选一号管写起来顺手。3.3 四种转移的一个不漏当前状态是 (s, i, j)我们看下一步两个选手分别从哪个管道取珠。为了方便描述用“一管”表示第一条管道用“二管”表示第二条管道。一号取一管二号取一管。需要 i1 n 且 j1 n然后比较 a[i1] 和 a[j1] 是否相等。如果相等新状态是 dp[s1][i1][j1]。一号取一管二号取二管。需要 i1 n 且 s-j1 m比较 a[i1] 和 b[s-j1] 是否相等。如果相等新状态是 dp[s1][i1][j]。这里 s-j 是二号选手已经取走二管珠子的数量所以下一步要取的是二管的第 s-j1 颗。一号取二管二号取一管。需要 s-i1 m 且 j1 n比较 b[s-i1] 和 a[j1] 是否相等。如果相等新状态是 dp[s1][i][j1]。一号取二管二号取二管。需要 s-i1 m 且 s-j1 m比较 b[s-i1] 和 b[s-j1] 是否相等。如果相等新状态是 dp[s1][i][j]。这里最容易写错的点是二管的下标。很多人会把 b[s-i1] 写成 b[i1]这就是没搞清楚坐标含义。i 只是“一号管”的消耗量不是总步数二号管的下标永远要用“总步数减去一号管消耗量”来算。我把四种转移整理成一张表写代码的时候直接对表检查一号选手选择二号选手选择合法性条件颜色相等条件新状态一管一管i1n, j1na[i1]a[j1](i1, j1)一管二管i1n, s-j1ma[i1]b[s-j1](i1, j)二管一管s-i1m, j1nb[s-i1]a[j1](i, j1)二管二管s-i1m, s-j1mb[s-i1]b[s-j1](i, j)当两个人取出的珠子颜色不同时这条转移直接丢弃不需要保存任何东西因为状态本身的定义就是“到目前为止每一步颜色都匹配成功”。4. 滚动数组落地代码里最容易写错的不是转移本身4.1 为什么必须滚动dp[s][i][j] 如果全部保留总状态数是 (nm1)×(n1)×(n1)。n 和 m 到 500 量级时大概是 1000×500×500四舍五入 2.5 亿个 int按 4 字节算要 1GB 左右普通比赛环境直接超限。但我们观察转移方向状态只会从 s 层走到 s1 层不会跨层。所以 s 这一维完全可以滚动数组开成 dp[2][MAXN][MAXN]两层交替使用。这样空间立刻降到 2×(n1)×(n1)约 2MB非常舒适。滚动数组有一个容易翻车的地方每次进入新的一层之前必须先把下一层清空。如果你不清空上一轮残留的旧值还留在数组里转移累加时就会把不存在的方案也算进去。尤其是我们使用“叠加”式的转移不清空会直接导致答案偏大。4.2 参考实现下面是一份完整的 C 参考实现。我把状态命名和题面保持一致方便对照。#include cstdio #include algorithm using namespace std; const int MOD 1024523; const int MAXN 505; int dp[2][MAXN][MAXN]; char a[MAXN], b[MAXN]; inline void add(int x, int y) { x y; if (x MOD) x - MOD; } int main() { int n, m; scanf(%d%d, n, m); scanf(%s%s, a 1, b 1); dp[0][0][0] 1; for (int s 0; s n m; s) { int cur s 1; int nxt cur ^ 1; // 清空下一层 for (int i 0; i n; i) for (int j 0; j n; j) dp[nxt][i][j] 0; for (int i 0; i n; i) { if (i s) continue; int si s - i; // 一号选手已经取走的二管珠子数 if (si m) continue; for (int j 0; j n; j) { if (j s) continue; int sj s - j; // 二号选手已经取走的二管珠子数 if (sj m) continue; int val dp[cur][i][j]; if (!val) continue; // 一号取一管二号取一管 if (i 1 n j 1 n a[i 1] a[j 1]) add(dp[nxt][i 1][j 1], val); // 一号取一管二号取二管 if (i 1 n sj 1 m a[i 1] b[sj 1]) add(dp[nxt][i 1][j], val); // 一号取二管二号取一管 if (si 1 m j 1 n b[si 1] a[j 1]) add(dp[nxt][i][j 1], val); // 一号取二管二号取二管 if (si 1 m sj 1 m b[si 1] b[sj 1]) add(dp[nxt][i][j], val); } } } printf(%d\n, dp[(n m) 1][n][n]); return 0; }代码里我用了i s和si m两个小判断来跳过非法状态一号选手总步数只有 s 步他从一管取的珠子数当然不能超过 s同时他从二管取走的 si 也不能超过二管总长 m。j 的判断同理。这些提前剪枝既能让程序少跑无用状态也能防止数组越界。add函数里只用了一次if (x MOD) x - MOD;。因为 dp 数组里任何位置在取模后一定小于 MOD再加一个也小于 MOD 的值结果一定小于 2×MOD所以一次减法一定够。不要在传输过程中随便用% MOD那个常数会让本来边缘的复杂度雪上加霜。4.3 一个极小的手工验证为了确认状态设计没理解错可以手工跑一个 n1、m1 的例子。假设两条管道里的珠子颜色都是 X也就是 a[1]Xb[1]X。最终能生成的颜色序列只有一个XX。它有两种取法先取一管再取二管或者先取二管再取一管。所以 f(XX)2答案应该是 4。用 DP 看s0 时只有 (0,0) 有值 1。s1 时因为两条管道第一颗颜色一样四种转移全部合法于是 (1,1)、(1,0)、(0,1)、(0,0) 各得到 1。s2 时最终状态只剩下 (1,1)四个前驱状态都能通过各自剩余的管道转移到 (1,1)所以最终 dp(1,1)4。如果两条管道颜色不同比如 a[1]Xb[1]Y那最终颜色序列有 XY 和 YX 两个各只有 1 种取法答案应该是 2。DP 在 s1 时只有“都取一管”和“都取二管”两种转移合法给 (1,1) 和 (0,0) 各贡献 1s2 时它们各自再转移到 (1,1)最终得 2。一切符合预期。5. 边界、模数与延伸思考把每日一题的价值榨干5.1 二管下标的镜像错误这个题最常见的 bug 就是二管下标写错。我见过有人把“二号选手取二管的下一步下标”写成sj1这是对的但同一份代码里写“一号选手取二管的下一步下标”时却不小心照抄成sj1这就是错的。一号选手的二管消耗量是si不是sj。为什么会犯这个错因为状态里 i 和 j 都是“一号管消耗量”长得很像。解决方法是每次写转移前先在纸上把四个量明确写出来i一号选手已经取走的一管数量si一号选手已经取走的二管数量si s - ij二号选手已经取走的一管数量sj二号选手已经取走的二管数量sj s - j只要这四个量能随时从脑子里蹦出来二管索引就不会乱。如果直接背着写代码很容易把 s-i 和 s-j 搞混。这道题的思维难点不在算法设计而在把坐标语义贯彻到每一行代码里。5.2 数组尺寸与清空策略dp 的第二维和第三维都开成 MAXN因为状态中的 i 和 j 都表示“一管消耗量”而一管长度最多是 n。不要错误地以为第二维要开 m。如果最后循环边界写成j m遇到 n 和 m 不同的数据时会漏掉大量合法状态。清空下一层时我用的是两层嵌套循环逐格清零。这个写法的优点是逻辑清楚缺点是常数略大。如果你追求极致性能可以用memset(dp[nxt], 0, sizeof(dp[nxt]));。但注意dp[nxt]是二维数组的首地址sizeof(dp[nxt])是整个二维数组的字节数直接一次清干净。两种写法学哪种都可以关键是别漏清。还有一个小细节初始状态dp[0][0][0] 1放在清空逻辑之前还是之后都无所谓因为 dp 是全局数组初始全零。但如果你用 vector 动态创建记得先初始化再赋初值。我习惯把所有层显式清一遍再设dp[0][0][0]1这样永远不会有历史残留问题。5.3 复杂度估算和滚动后的思考在 n 和 m 都是 500 的量级下外层 s 有 nm 约 1000 层每层 i 和 j 的范围是 500×500总状态数约 2.5 亿个。每个状态最多做四次颜色比较和四次加法在 C 里属于可跑的边缘范围。实际提交时自己本机跑一遍最恶劣数据会有数感如果超过两秒优先检查是不是没有做合法性剪枝或者清空层用了太大的冗余范围。如果某个数据版本把 n、m 提到 1000传统 O((nm)×n×m) 的做法就会吃紧。这时可以进一步优化剪枝利用 i 和 j 都必须满足0 s-i m这个范围把每层的合法 i、j 边界动态计算出来而不是傻傻地从 0 枚举到 n。代码会变难看一点点但常数明显下降。5.4 这个套路还能迁移到哪里平方和的双重计数思想在这道题里表现得特别典型。以后碰到形如“统计每个结果出现次数的平方之和”的题第一反应就应该是能不能把平方拆成两个相同游戏同时进行如果题目要你求 f(S)^3那就是三个人同时取珠子状态多一个人复杂度再乘一个维度。如果题目要求 f(S)^2 但两个玩家条件不对称比如第二个人每一步不能和第一个人的某种选择撞车那也只是在转移里多加一条限制底层思路不变。我个人做完这道题之后最大的收获是不要看到平方就害怕平方本质是给自己复制一个同样的世界然后让两个世界保持同步。最后分享一个我写这种双人 DP 的小习惯先老老实实把四维状态写在草稿纸上标清楚每个坐标的含义再去找一个线性关系压缩成三维。跳过四维直接写三维很容易在边界判断和下标换算上出错。四维到三维的过程才是这个题目真正想让你练的东西。