結果

問題 No.1483 Many Graph in Namori
ユーザー beet
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 HERE
signed 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 loop
for(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 descents
for(int u:T[v])
ans+=(inv.pow(sz[v]-sz[u])-M(1))*dp[u];
// see from v
M 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 loop
for(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
// prepare
int 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);
// add
for(int r:in_loop){
// see from r's subtree
// M pre=ans;
ans+=MFP([&](auto dfs,int v)->M{ // OK
M 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 left
ans+=(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0