用c++解决:题目描述 国王为了能够集中自己的权力,稳固城邦,她对国家道路设计要求十分严苛,任何两个城市之间的路径至多只有一条不经过首都,虽然但是,没有人知道为什么这样能够更好地稳固 X 国。 有一天,X 国国王决定巡视所有的城市,她通过无线电在巡城前一天向所有的城市通知了这个好消息。热情的群众们也积极地做出了响应,准备迎接国王的到来。 国王一天只能造访一座城市,而且第一天她会从首都开始。 在之后的每一天,她会随机从与她所在城市直接相连的城市中等概率地选择一个她没有前往过的城市前往。如果不存在这样的城市,她会立即原路返回,从她来这个城市的路回去,再重复上述操作,因为有携带宇宙射线的传送门,这个过程不消耗时间。 爱戴她的群众们想要知道,他们的国王第一次到达他们所在城市的日期(她造访首都的那一天为 11,之后每一天一次加 11)的期望是多少,答案对 998244353998244353 取模。 保证城市构成的图是连通图,无自环与重边,且首都编号为 11。 输入格式 第一行有两个数 n,mn,m,代表X国的城市数和路径数。 接下来的 mm 行,每行两个数 u,vu,v 表示城市的一条路径。 输出格式 共 nn 行,每行一个数。 第 ii 行代表 ii 号城市的期望。
时间: 2024-04-09 17:32:00 浏览: 19
这个问题可以使用动态规划来解决。我们可以定义dp[i]为第i天国王第一次到达城市i的期望。
首先,我们初始化dp数组为0,表示国王第一次到达任何城市的期望都是0。
然后,我们从第一天开始遍历到第n天。对于每一天i,我们遍历所有的城市j,计算国王第一次到达城市j的期望。
对于每个城市j,我们需要考虑两种情况:
1. 如果国王第一次在第i天到达城市j,则这个期望值为i。
2. 如果国王第一次在第i天之前的某一天到达了与城市j直接相连的城市k,然后从k到j的路径上没有经过首都。在这种情况下,国王第一次到达城市j的期望值可以通过国王第一次到达城市k的期望值来计算。
因此,对于每个城市j,我们需要遍历它的所有直接相连的城市k,然后计算dp[j] += dp[k] / (k的出度 - 1)。
最后,我们输出dp数组中的每个元素。
以下是使用C++语言实现的代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
vector<int> outdegree(n + 1, 0);
vector<int> dp(n + 1, 0);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
outdegree[u]++;
outdegree[v]++;
}
dp[1] = 1;
for (int i = 1; i <= n; i++) {
for (int j : graph[i]) {
if (j != 1) {
dp[i] = (dp[i] + dp[j]) % MOD;
}
}
dp[i] = (dp[i] * (outdegree[i] - 1)) % MOD;
}
for (int i = 1; i <= n; i++) {
cout << dp[i] << endl;
}
return 0;
}
```
希望能对你有所帮助!如果还有其他问题,请随时提问。