E – King Bombee

题目描述：

n个点，m条边，求起点是s，终点是t，经过偶数次点x的长度为k+1的路径的数量

思路：

dp[i][j][k]表示从s开始，经过i条边后到达j，经过x的次数模2等于k的路径的数量

状态转移方程就很显然了

dp[i+1][v][0^p]+=dp[i][u][0]

dp[i+1][v][1^p]+=dp[i][u][1]

其中p=(v==x);

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int s, t, x;
vector<int>tr[2005];
ll dp[2005][2005][2];
void work(){
    cin >> n >> m >> k;
    cin >> s >> t >> x;
    for(int i = 1, a, b; i <= m; ++i){
        cin >> a >> b;
        tr[a].push_back(b);tr[b].push_back(a);
    }
    dp[0][s][0] = 1;
    for(int i = 0; i < k; ++i){
        for(int u = 1; u <= n; ++u){
            for(auto v : tr[u]){
                int p = (v == x);
                (dp[i + 1][v][0^p] += dp[i][u][0])%=mod;
                (dp[i + 1][v][1^p] += dp[i][u][1])%=mod;
            }
        }
    }
    cout << dp[k][t][0] << endl;
}


int main(){
    io;
    work();
    return 0;
}