题解：AT_abc372_f [ABC372F] Teleporting Takahashi 2

https://www.luogu.com.cn/problem/AT_abc372_f

简单易懂易写。

考虑一步一步走。要么顺着环走，要么走那 \(m\) 条边。

设 \(id(k, i) = (i - 1 - k) \bmod n + 1\)。

设 \(g_{k,id(k, i)}\) 表示走了 \(k\) 步走到 \(i\) 的方案数。

这样设计下标就不需要管顺着环走了。顺着环走的转移就是直接 \(g_{k+1,\cdots} = g_{k,\cdots}\) 整体转移。

如果第 \(k\) 步选择走 \(m\) 条边，对于边 \((u,v)\)，就是 \(g_{k,id(k,v)}\) 由 \(g_{k-1,id(k-1,u)}\) 转移来。记得转移的时候建临时数组。

实现可以直接省略第一维，具体可以看代码。

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<int, int>;

const int MAXN = 2e5 + 3;
const LL mod = 998244353;

int n, m, k;
PII eg[53];
LL dp[MAXN], tmp[MAXN];

int Ri(int t, int i){
  i--;
  return (i + t % n + n) % n + 1;
}
int _Ri(int t, int i){
  i--;
  return (i - t % n + n) % n + 1;
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> k;
  for(int i = 1; i <= m; i++){
    cin >> eg[i].first >> eg[i].second;
  }
  dp[1] = 1;
  for(int t = 1; t <= k; t++){
    for(int i = 1; i <= m; i++){
      int U = _Ri(t - 1, eg[i].first), V = _Ri(t, eg[i].second);
      tmp[U] = dp[U];
    }
    for(int i = 1; i <= m; i++){
      int U = _Ri(t - 1, eg[i].first), V = _Ri(t, eg[i].second);
      dp[V] = (dp[V] + tmp[U]) % mod;
    }
  }
  LL ans = 0;
  for(int i = 1; i <= n; i++){
    ans = (ans + dp[i]) % mod;
  }
  cout <<ans;
  return 0;
}