ABC372 F 题解

F - Teleporting Takahashi 2

先把问题转化一下：把环断开成链，复制 \((K + 1)\) 层，每走一步就相当于前进一层：

可以想到一个简单的 dp：设 \(f(i, j)\) 表示走到第 \(i\) 层第 \(j\) 个位置的方案数。

• 初始化：\(f(0, 1) = 1\)，其它均为 \(0\)，表示 Takahashi 从第 \(0\) 层的 \(1\) 位置出发。
• 答案统计：\(ans = \sum_{i = 1}^{N} f(K + 1, i)\)。
• 转移：\(f(i, j) = \sum_{v \in pre(j)} f(i - 1, v)\)，其中 \(pre(j)\) 能通过一条边直接到达 \(j\) 的点的集合。

上述做法的时空复杂度都是 \(O(NK)\)。由于每层的状态只和前一层有关，我们可以简单地用滚动数组把空间复杂度优化到 \(O(N)\)，但时间复杂度似乎不太好优化。（提交记录）

（下面为了方便，把点的编号转为从 \(0\) 开始。实际上，对于环上的问题，0-indexed 往往都更方便。）

突破口在于 \(M\)。我们先假设 \(M = 0\)。这时，所有的边都形如 \((i, i + 1)\)（在环的意义下），并且所有的点 \(j\) 都只能从前一层的 \(j-1\) 这一个位置转移过来，也就是 \(f(i, j) = f(i-1, j-1)\)。换句话说，我们把 \(f(i - 1, *)\) ”右移“一位就得到了 \(f(i, *)\)：

这启示我们转移时，不用暴力地赋值 \(f(i, *)\)，而是用一个变量 \(be\) 代表当前数组把哪个下标当作“\(1\)”，每次转移到下一层，就让 \(be \gets (be - 1) \bmod N\) （也就是在环上自减 \(1\)）。用 \(f'\) 表示代码中的数组：一开始在第 \(0\) 层，\(be = 1\)，于是 \(f'(1) = f(0, 1), f'(2) = f(0, 2), \dots, f'(N) = f(0, N)\)。转移到第 \(1\) 层以后，\(be = N\)，于是 \(f'(N) = f(1, 1), f'(1) = f(1, 2), \dots, f'(N-1) = f(N)\)。这样，转移时我们只需更新 \(be\)，而不用把 \(f'\) 全部扫一遍。

当 \(M \not= 0\) 时呢？我们注意到，只有 \(M\) 条边不是 \((i, i+1)\) 类型的，而 \(M \le 50\)，因此可以暴力地枚举这些边来转移。

具体实现时，下标转化的细节有点多。此外，为了防止新旧版本的 \(f'\) 混淆，我用了 map 来存储那些被 \(M\) 条边连接的点的值。这使得时间复杂度乘上一个 \(\log\)，或许更精细的做法可以去掉这个 \(\log\)，但我感觉用 map 方便一些。

时间复杂度 \(O(N + KM \log M)\)，空间复杂度 \(O(N + M)\)。

参考代码：

vector<int> f(N);
f[0] = 1;
int be = 0;
map<int, int> tmp;
for(int i = 1; i <= K; i++)
{
    tmp.clear();
    be = (be + N - 1) % N;
    for(auto ed: e)
    {
        int u = ed.u, v = ed.v;
        u = (be + 1 + u) % N, v = (be + v) % N;
        if(tmp.find(v) == tmp.end()) tmp[v] = f[v];
        tmp[v] = (f[u] + tmp[v]) % MOD;
    }
    for(auto p: tmp)
        f[p.first] = p.second;
}

int ans = 0;
for(int x: f)
    ans = (ans + x) % MOD;
cout << ans << endl;

提交记录

（注：图源：ATcoder 的官方题解）

G - Ax + By < C

咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕

while(1) printf("gugugu");

I can't solve this problem by myself.