题目大意
给定一张缺少了 \(m\) 条边的 \(n\) 个点的完全图和一个正整数 \(k\)，你需要求出满足以下条件的序列 \(A\) 的数量：
- \(A\) 的长度为 \(k+1\)。
- \(A_0=A_k=1\)。
- \(\forall 0\le i\le k-1\)，点 \(A_i\) 和点 \(A_{i+1}\) 之间存在边。
思路分析
图上计数，考虑 DP。
设 \(f_{i,j}\) 表示考虑到路径上的第 \(i\) 个点（从 \(0\) 开始），当前位于点 \(j\) 的方案数。
那么所求的就是 \(f_{k,1}\)。
考虑状态转移，因为给出的是原图的补图，所以可以列出方程：
\[f_{i,j}=\sum_{k=1}^nf_{i-1,k}-\sum_{v\in e_j}f_{i-1,v}-f_{i-1,j}
\]
其中，\(e_i\) 表示点 \(i\) 在补图中的出点集合。
容易发现，前半部分可以通过记录前缀和的方式优化掉，所以就做完了，时间复杂度和空间复杂度均为 \(O(n^2)\)（视 \(n,m\) 同阶），也可以通过滚动数组将空间优化到 \(O(n)\)，但无所谓了。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=10100,M=5050,mod=998244353;
#define int long long
int to[N],nxt[N],head[N];
int idx=1,n,m,k,in1,in2,sum;
int f[M][M];
void add(int u,int v){
idx++;to[idx]=v;nxt[idx]=head[u];head[u]=idx;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=m;i++){
scanf("%lld%lld",&in1,&in2);
add(in1,in2);add(in2,in1);
}
f[0][1]=1;//第 0 天在点 1 有一种方案
for(int i=1;i<=k;i++){
sum=0;
for(int s=1;s<=n;s++) sum+=f[i-1][s];//记录和
for(int s=1;s<=n;s++){
f[i][s]=sum-f[i-1][s];
for(int j=head[s];j;j=nxt[j]){
int v=to[j];
f[i][s]-=f[i-1][v];//依次减去
}
f[i][s]%=mod;
}
}
cout<<f[k][1]<<'\n';
return 0;
}