您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

E - King Bombee

传送门

E - King Bombee

题意:给你一个图,可以经过任意边k次,其中一个点x必须经过偶数次,求从起点s到终点t的方案数。

分析:dp写不来,还是dfs舒服。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,m,k,s,t,x;
vector<int>mp[2005];
int dp[2005][2005][2];

int dfs(int step,int u,int even)
{
	if(step==k) return u==t&&even;
	if(~dp[step][u][even]) return dp[step][u][even];
	int ans=0;
	for(auto v:mp[u])
	{
		ans+=dfs(step+1,v,even^(v==x));
		ans%=mod;
	}
	dp[step][u][even]=ans;
	return ans;
}

signed main()
{
	cin>>n>>m>>k>>s>>t>>x;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	memset(dp,-1,sizeof dp);
	cout<<dfs(0,s,1)<<endl;
}


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进