Atcoder 212E Safety Journey

Problem Statement

The Republic of AtCoder has N cities, called City 1, City 2, ……, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1≤i≤M, the road connecting City Ui and City Vi has become unusable.

Takahashi will go for a KK-day trip that starts and ends in City 1. Formally speaking, a KK-day trip that starts and ends in City 1 is a sequence of K+1 cities (A0,A1,…,AK) such that A0=AK=1 holds and for each 0≤i≤K−1, Ai and Ai+1 are different and there is still a usable road connecting City Ai and City Ai+1.

Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A0,A1,…,AK) and (B0,B1,…,BK) are said to be different when there exists an i such that Ai≠Bi.

Constraints

2≤N≤5000
0≤M≤min(N(N−1)2,5000)
2≤K≤5000
1≤Ui<Vi≤N
All pairs (Ui,Vi) are pairwise distinct.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K
U1 V1
::
UM VM

Output

Print the answer.

Sample Input 1 Copy

3 1 4
2 3

Sample Output 1 Copy

There are four different trips as follows.

(1,2,1,2,1)
(1,2,1,3,1)
(1,3,1,2,1)
(1,3,1,3,1)

No other trip is valid, so we should print 44.

Sample Input 2 Copy

Sample Output 2 Copy

No road remains usable, so there is no valid trip.

Sample Input 3 Copy

Sample Output 3 Copy

428417047

题目翻译

(N)座城市，每对城市间有双向道路，有(M)条道路无法使用

从城市(1)出发，旅行(K)天，最后一天回到(1)。旅游城市序列(A_0,A_1,...A_k)，其中(A_0=A_k=1)，共有多少不同旅行方案

(2<=N<=5000)

(M<=min(frac{N*(N-1)}{2},5000))

(2<=K<=5000)

题目解析

首先考虑最简单的做法，令(f[j][i])表示第(i)天在城市(j)

枚举天数(i)，和停留的城市(j)进行转移

但题目给出的(M)条边是不可通行的道路，如果枚举所有可行道路，复杂度将达到(O(K*N^2))，不符合数据范围

考虑到(f[j][i]=sum_{k=1}^{n}{f[k][i-1]}-sum_{k不可达}{f[k][i-1]}-f[j][i-1])

(sum_{k=1}^{n}{f[k][i-1]})可以(O(N))求出，(sum_{k不可达}{f[k][i-1]})可以(O(M))求出

总复杂度为(O(K*(N+M)))

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
struct Node{
    int next,to;
}edge[10005];
int n,m,k;
int head[5005],num,f[5005][5005],Mod=998244353;
void add(int u,int v){
    num++;
    edge[num].next=head[u];
    head[u]=num;
    edge[num].to=v;
}
int main(){
    int u,v;
    cin>>n>>m>>k;
    for (int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    memset(f,0,sizeof(f));
    f[1][0]=1;
    for (int i=1;i<=k;i++){
        int sum=0;
        for (int j=1;j<=n;j++)
        sum=(sum+f[j][i-1])%Mod;
        for (int j=1;j<=n;j++){
            f[j][i]=(sum-f[j][i-1]+Mod)%Mod;
            for (int k=head[j];k;k=edge[k].next){
                int v=edge[k].to;
                f[j][i]=(f[j][i]-f[v][i-1]+Mod)%Mod;
            }
        }
    }
    cout<<f[1][k]<<endl;
}