結果
問題 | No.1483 Many Graph in Namori |
ユーザー |
![]() |
提出日時 | 2021-03-15 17:41:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 5,436 bytes |
コンパイル時間 | 2,975 ms |
コンパイル使用メモリ | 223,156 KB |
最終ジャッジ日時 | 2025-01-19 17:18:00 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 56 |
ソースコード
#include <bits/stdc++.h>using namespace std;using Int = long long;const char newl = '\n';template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}template<typename T=int>vector<T> read(size_t n){vector<T> ts(n);for(size_t i=0;i<n;i++) cin>>ts[i];return ts;}template<typename T, T MOD = 1000000007>struct Mint{static constexpr T mod = MOD;T v;Mint():v(0){}Mint(signed v):v(v){}Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}Mint pow(long long k){Mint res(1),tmp(v);while(k){if(k&1) res*=tmp;tmp*=tmp;k>>=1;}return res;}static Mint add_identity(){return Mint(0);}static Mint mul_identity(){return Mint(1);}Mint inv(){return pow(MOD-2);}Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}Mint& operator/=(Mint a){return (*this)*=a.inv();}Mint operator+(Mint a) const{return Mint(v)+=a;}Mint operator-(Mint a) const{return Mint(v)-=a;}Mint operator*(Mint a) const{return Mint(v)*=a;}Mint operator/(Mint a) const{return Mint(v)/=a;}Mint operator-() const{return v?Mint(MOD-v):Mint(v);}bool operator==(const Mint a)const{return v==a.v;}bool operator!=(const Mint a)const{return v!=a.v;}bool operator <(const Mint a)const{return v <a.v;}static Mint comb(long long n,int k){Mint num(1),dom(1);for(int i=0;i<k;i++){num*=Mint(n-i);dom*=Mint(i+1);}return num/dom;}};template<typename T, T MOD> constexpr T Mint<T, MOD>::mod;template<typename T, T MOD>ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}template<typename F>struct FixPoint : F{FixPoint(F&& f):F(forward<F>(f)){}template<typename... Args>decltype(auto) operator()(Args&&... args) const{return F::operator()(*this,forward<Args>(args)...);}};template<typename F>inline decltype(auto) MFP(F&& f){return FixPoint<F>{forward<F>(f)};}//INSERT ABOVE HEREsigned main(){cin.tie(0);ios::sync_with_stdio(0);int n,k;cin>>n>>k;vector<set<int>> S(n);for(int i=0;i<n;i++){int a,b;cin>>a>>b;a--;b--;S[a].emplace(b);S[b].emplace(a);}vector<vector<int>> T(n);queue<int> que;for(int i=0;i<n;i++)if(S[i].size()==1)que.emplace(i);while(!que.empty()){int v=que.front();que.pop();int p=*S[v].begin();T[p].emplace_back(v);S[p].erase(v);S[v].erase(p);if(S[p].size()==1)que.emplace(p);}vector<int> in_loop=[&](){int pos=-1;for(int i=0;i<n;i++)if(S[i].size()>0) pos=i;assert(~pos);vector<int> res;while(not S[pos].empty()){res.emplace_back(pos);int nxt=*S[pos].begin();S[pos].erase(nxt);S[nxt].erase(pos);pos=nxt;}return res;}();using M = Mint<int, 998244353>;M ans{0};vector<M> dp(n);vector<int> sz(n);M inv=(M(1)-M(k)).inv();// not use loopfor(int r:in_loop){MFP([&](auto dfs,int v)->void{sz[v]=1;for(int u:T[v]){dfs(u);sz[v]+=sz[u];}dp[v]=inv.pow(sz[v])-M(1);for(int u:T[v])dp[v]+=dp[u]*inv.pow(sz[v]-sz[u]);// see from descentsfor(int u:T[v])ans+=(inv.pow(sz[v]-sz[u])-M(1))*dp[u];// see from vM zero=1;M one=0;M all=inv.pow(sz[v]-1);for(int u:T[v])one+=inv.pow(sz[u])-M(1);ans+=M(k)*inv*zero;ans+=M(k)*inv*one;ans+=inv*(all-(zero+one));// cout<<v<<':'<<(all-(zero+one))<<endl;})(r);}// cout<<ans/inv.pow(n)<<endl;auto calc1=MFP([&](auto dfs,int r,int v)->M{M res=inv.pow(sz[v])-M(1);if(v==r) res+=M(1);for(int u:T[v]) res+=dfs(r,u)*inv.pow(sz[v]-sz[u]);return res;});// use all edges in loopfor(int r:in_loop)ans+=calc1(r,r)*inv.pow(n-sz[r]);// cout<<ans/inv.pow(n)<<endl;auto calc2=MFP([&](auto dfs,int r,int v)->M{M res=inv.pow(sz[v])-M(1);if(v==r) res=inv*(inv.pow(sz[v]-1)-M(1))+inv;for(int u:T[v]) res+=dfs(r,u)*inv.pow(sz[v]-sz[u]);return res;});// use partial edges in loop// prepareint num=0;M sum{0};M uku{0};auto proceed=[&](int r){sum*=inv.pow(sz[r]);uku*=inv.pow(sz[r]);// cout<<r<<"+"<<calc2(r,r)*inv.pow(num+n)<<endl;sum+=calc2(r,r)*inv.pow(num+n);uku-=M(1);num+=sz[r];};for(int r:in_loop) proceed(r);assert(num==n);// addfor(int r:in_loop){// see from r's subtree// M pre=ans;ans+=MFP([&](auto dfs,int v)->M{ // OKM res=inv.pow(sz[v])-M(1);for(int u:T[v])res+=dfs(u)*inv.pow(sz[v]-sz[u]);return res;})(r)*(inv.pow(n-sz[r])-M(1));// cout<<r<<':'<<(ans-pre)/inv.pow(n)<<endl;// cout<<r<<'-'<<calc2(r,r)*inv.pow(num-n)*inv.pow(n-sz[r])<<endl;sum-=calc2(r,r)*inv.pow(num+n-n)*inv.pow(n-sz[r]);uku+=M(1)*inv.pow(n-sz[r]);// see from leftans+=(sum/inv.pow(num+sz[r])+uku)*(inv.pow(sz[r])-M(1));// cout<<r<<':'<<sum/inv.pow(num+sz[r])<<' '<<uku<<' '<<(inv.pow(sz[r])-M(1))<<endl;proceed(r);}ans/=inv.pow(n);cout<<ans<<newl;return 0;}