E - Safety Journey
题意：
n
n
n 个点，起初是个完全图，删除
m
m
m 条边。起点为
1
1
1，经过
k
k
k 个点后，终点也为
1
1
1。也就是求存在多少种不同的序
(
A
0
,
A
1
,
A
2
,
.
.
.
,
A
k
)
(A_0,A_1,A_2,...,A_k)
(A0,A1,A2,...,Ak)，满足
A
0
=
A
k
=
1
A_0 = A_k = 1
A0=Ak=1。答案对
998244353
998244353
998244353 取模
思路：
考虑
f
[
i
]
[
j
]
f[i][j]
f[i][j] 表示从 1 出发第
i
i
i 天以
j
j
j 城市结尾的方案数
f
[
0
]
[
1
]
=
1
f[0][1]=1
f[0][1]=1
f
[
i
]
[
j
]
=
∑
d
=
1
k
f
[
i
−
1
]
[
d
]
(
d
到
j
有
边
)
f[i][j]=\sum_{d=1}^k f[i-1][d](d \, 到 \, j 有边)
f[i][j]=∑d=1kf[i−1][d](d到j有边)
可以反过来考虑，用上一层总的方案数减去不满足的方案数
code：
#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define eps 1e-6
using namespace std;
const int maxn = 5e3 + 9;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m, k;
vector <int> v[maxn];
ll f[maxn][maxn];// 从 1 出发第 i 天以 j 城市结尾
void work()
{
cin >> n >> m >> k;
for(int i = 1, x, y; i <= m; ++i){
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
f[0][1] = 1;
for(int i = 1; i <= k; ++i){
ll sum = 0;
for(int j = 1; j <= n; ++j)
sum += f[i-1][j];
for(int j = 1; j <= n; ++j)
{
f[i][j] = (f[i][j] + sum - f[i-1][j] + mod) % mod;// 原地踏步
for(int d = 0; d < v[j].size(); ++d)// 被删除的边产生的方案数
f[i][j] = (f[i][j] - f[i-1][v[j][d]] + mod) % mod;
}
}
cout << f[k][1];
}
int main()
{
ios::sync_with_stdio(0);
// int TT;cin>>TT;while(TT--)
work();
return 0;
}