[数据结构与算法]AtCoder Beginner Contest 244 E 线性dp 动态规划 图论

题目

给你N个点M条无向边。
要求
求出从点S出发，点T为终点的路径中路径长度为K且经过点X偶数次（包括0次）的路径数有多少条。
N <= 2000
M <= 2000
答案对998244353取模

题解思路

想了半天什么dfs什么组合数学都出来了。
直接dp
f[i][j][k] 走了i步停在j点经过X点的奇偶性为k（0或者1)的路径数。
初始化
f[0][s][0] = 1 ;
转移
对于k步枚举所有边，如果是X点就改变k的奇偶性，不是就直接加。

AC代码

#include <bits/stdc++.h>
//#include <unordered_map>
//priority_queue
#define PII pair<int,int>
#define ll long long

using namespace std;

const  int  INF =  0x3f3f3f3f ;
const  int  N =  200100 ;
const int mod = 998244353 ; 
vector <PII> sk ; 
long long f[2010][2010][3] ; 
void solve()
{
    int n , m , k , s , t , x ;
    cin >> n >> m >> k >> s >> t >> x ; 
    for (int i = 1 ; i <= m ; i++ )
    {
        int t1 , t2 ;
        cin >> t1 >> t2 ;
        sk.push_back({t1,t2}) ; 
    }
    f[0][s][0] = 1 ; 
    for (int i = 1 ; i <= k ; i++ )
    {
        for ( auto j : sk )
        {
            for (int u = 0 ; u <= 1 ; u++ )
            {
                if ( j.first == x )
                {
                    f[i][j.first][u] = (f[i][j.first][u] + f[i-1][j.second][(u+1)%2] )%mod ; 
                    f[i][j.second][u] = (f[i][j.second][u] + f[i-1][j.first][u] )%mod ;
                }else if ( j.second == x )
                {
                    f[i][j.second][u] = (f[i][j.second][u] + f[i-1][j.first][(u+1)%2] )%mod ;
                    f[i][j.first][u] = (f[i][j.first][u] + f[i-1][j.second][u] )%mod ; 
                }
                else 
                {
                    f[i][j.first][u] = (f[i][j.first][u] + f[i-1][j.second][u] )%mod ; 
                    f[i][j.second][u] = (f[i][j.second][u] + f[i-1][j.first][u] )%mod ;
                }
            }
        }
    }
    cout << f[k][t][0] << "\n" ; 
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
        solve() ;
    return 0 ;
}