整体思想以及取模

2024-08-21 11:52

文章标签 整体思想取模

本文主要是介绍整体思想以及取模，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：一开始由于失误，误以为分数相加取模不能，但是其实是可以取模的

这个题目如果按照一般方法，到达每个节点再进行概率统计，但是不知道为什么只过了百分之十五的测试集

题目地址
在这里插入图片描述

附上没过关的代码

#include<bits/stdc++.h>
using namespace std;#define int long longint n; int ans = 0;
const int N = (int)2e6 + 5;
const int Mod = 998244353;
int e[N], ne[N], h[N / 2], idx = 0;
void add(int a, int b) {e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}int qw(int x, int p) {int temp = 1;while (p) {if(p&1)temp = x * temp % Mod;x = x * x % Mod;p >>= 1;}return temp;
}void dfs(int u, int fa, int g, int step) {int cnt = 0;for (int i = h[u]; i; i = ne[i]) {int v = e[i]; if (fa == v) continue;cnt++;}if (cnt == 0) {// 已经是子节点了 //ans = (ans + (step % Mod) * qw(g, Mod - 2)) % Mod; return;ans = (ans + step*g%Mod) % Mod; return;}g = (g % Mod) * (qw(cnt, Mod - 2) % Mod) % Mod;for (int i = h[u]; i; i = ne[i]) {int v = e[i]; if (fa == v) continue;dfs(v, u, g , step + 1);}
}signed main() {cin >> n;for(int i=1;i<n;i++){int u,v; cin >> u >> v;add(u,v),add(v,u);}if(n==1){cout << 0 ; return 0;}dfs(1,0,1,0);cout << ans;return 0;
}

再写一个过关的，按照官方答案的解法的

#include<bits/stdc++.h>
using namespace std;#define int long longint n; int ans = 0;
const int N = (int)2e6 + 5;
const int Mod = 998244353;
const int P = 998244353;
int e[N], ne[N], h[N / 2], idx = 0;
vector<int> a[N / 2];
int siz[N], ye[N]; // 记录每一层的节点个数以及叶子节点的个数 
void add(int a, int b) {e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}int qw(int x, int p) {int temp = 1;while (p) {if (p & 1)temp = x * temp % Mod;x = x * x % Mod;p >>= 1;}return temp;
}void dfs(int u, int fa, int dep) {int cnt = 0; siz[dep]++;for (int i = h[u]; i; i = ne[i]) {int to = e[i]; if (to == fa) continue;cnt++; dfs(to, u, dep + 1);}if (cnt == 0) {ye[dep]++;}
}void solve() {int pre = 1; // 概率for (int i = 1; i < n; i++) {//cout << " siz " << i << " " << ye[i] << endl;if (siz[i] == 0) break;//ans = (ans+(pre*(ye[i]*(qw(siz[i],Mod-2),Mod-2)%Mod)%Mod) * (i)%Mod) % Mod;ans = (ans + pre * ye[i] % P * qw(siz[i], P - 2) % P * (i) % P) % P;pre = pre * ((siz[i] - ye[i]) * (qw(siz[i], Mod - 2)) % Mod)%Mod;//pre = pre * (((siz[i] - ye[i]) % P + P) % P) % P * qw(siz[i], P - 2) % P;}cout << ans; return;
}signed main() {cin >> n;for (int i = 1; i < n; i++) {int u, v; cin >> u >> v;add(u, v), add(v, u);//a[u].push_back(v); a[v].push_back(u);}if (n == 1) {cout << 0; return 0;}dfs(1, 0, 0);solve();return 0;
}