题解：P12607 三叉求和

gcx12012 · 2025-05-25 19:59:23 · 题解

前言

作为赛时通过选手贡献一个搞笑做法。

Solution

我们不难想到一个 O(n^3) 的 dp：设 f_{i,j,k} 表示当前考虑到第 i 位，前 i 位的三进制数位和为 j，第 i 位对前一位的进位贡献为 k。

然后直接根据题目转移即可，考虑 k 只能取 \frac{j}{3} 到 \frac{j}{2} 之间的整数，这是显然的，然后 dp 值为 0 的不转移，再稍微卡一下别的就能过题了。

代码比较简单，就不放了。