题意

给出一个 \(n\) 个点的有向图，点 \(i\) 连向点 \((i+1)\)，点 \(n\) 连向点 \(1\)。再给你 \(m\) 条额外边。你的初始位置为 \(1\)，问你移动 \(k\) 步的不同方案数（仅当路径不同时两个方案不同）。

思路

先想怎样暴力转移，显然移动 \(k\) 步到达一个点的方案数为所有跟这个点连边的移动 \((k-1)\) 步到达的点的方案数的总和，时间复杂度 \(O((n+m)k)\)，显然不能接受。
可以发现 \(m\le 50\)，考虑优化掉 \(n\)。最开始的 \(n\) 条初始边构成了一个环，所以每个点 \(i\) 都一定会从 \((i-1)\) 转移过来，也就是环上的数整体右移一位。我们换位思考，不去右移环上的数，而是整体左移一位额外边上的数，时间复杂度就会大大减小了。因为最外圈是个环，所以整体左移额外边虽然会改变连边关系，但是不会改变边的相对位置，对答案不会造成影响。时间复杂度 \(O(mk)\)，可以通过。

代码

#include<bits/stdc++.h>
#define md 998244353
using namespace std;
int n,m,k,num[200005],ANS;
vector<int> t[200005],pt;
int to(int x,int i){//将点x左移i位，注意取模
	return ((x-i-1)%n+n)%n+1;
}
signed main(){
	cin>>n>>m>>k;
	num[1]=1;
	for(int x,y,i=1;i<=m;i++){
		cin>>x>>y;
		if(!t[x].size())
			pt.push_back(x);
		t[x].push_back(y);
	}
	for(int i=0;i<k;i++){//这里先从额外边转移再整体左移，所以i从0开始
		vector<pair<int,int>> cge;
		for(int v:pt)
			for(int v2:t[v])
				cge.push_back({num[to(v,i)],to(v2,i+1)});//因为整体左移，所以从原来的u->v变为了u->(v-1)
		for(pair<int,int> v:cge)
			num[v.second]=(1ll*num[v.second]+v.first)%md;
	}
	for(int i=1;i<=n;i++)
		ANS=(ANS+num[i])%md;
	cout<<ANS;
	return 0;
}