UOJ#181.【UR#12】密码锁

一个竞赛图&＃xff0c;其中m条边&＃xff0c;方向为x−>y(x<y)x−>y(x的概率是pipi&＃xff0c;y−>xy−>x的概率是1−pi1−pi&＃xff0c;其他边两个方向的概率都是1212
求强连通分量的期望个数

竞赛图缩点后一定是一条链&＃xff0c;前面的点连向后面所有点&＃xff0c;我们定义点集SS是这条链的一个前缀当且仅当S⊂V,S和V−S之间的边全部由S连向V−S$S\subset V,S和V-S之间的边全部由S连向V-S$
那么强连通分量个数等价于缩点后链的前缀SS的个数+1

一种想法是枚举点集S$S$&＃xff0c;计算这些边的贡献&＃xff0c;但nn很大，2n$2^n$不能接受
一个大小为xx的前缀，如果连出去的没有特殊边，他的贡献是(12)x(n−x)$(\frac{1}{2}{)}^{x(n-x)}$&＃xff0c;每有一条概率为pp的特殊边，贡献乘上2p$2p$
因为mm很小，一个m$m$条边的联通块至多m&＃43;1m&＃43;1个点&＃xff0c;我们只考虑特殊边&＃xff0c;对每个联通块枚举SS里的点，计算S$S$有xx个点在这个联通块里的贡献和
最后再对所有联通块做个背包合并起来

code&＃xff1a;

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;const int maxn &＃61; 50;
const int mod &＃61; 998244353;
inline void add(int &a,const int &b){a&＃43;&＃61;b;if(a>&＃61;mod)a-&＃61;mod;}int pw(int x,int k)
{int re&＃61;1;for(;k;k>>&＃61;1,x&＃61;(ll)x*x%mod) if(k&1)re&＃61;(ll)re*x%mod;return re;
}
int inv(int x){ return pw(x,mod-2); }int n,m,Inv;
int e[maxn][4];
struct edge{int y,i,nex;}a[maxn*maxn]; int len,fir[maxn];
inline void ins(const int x,const int y,const int i){a[&＃43;&＃43;len]&＃61;(edge){y,i,fir[x]};fir[x]&＃61;len;}vector<int>V[maxn],Ve[maxn];
int vis[maxn],cnt,id[maxn];
void dfs(const int x)
{V[vis[x]&＃61;cnt].push_back(x); id[x]&＃61;(int)V[cnt].size();for(int k&＃61;fir[x],y&＃61;a[k].y;k;k&＃61;a[k].nex,y&＃61;a[k].y)if(xfor(int k&＃61;fir[x],y&＃61;a[k].y;k;k&＃61;a[k].nex,y&＃61;a[k].y) if(!vis[y])dfs(y);
}
int sum[1<<20],g[maxn][maxn];
void Solve(const int now)
{int vn&＃61;(int)V[now].size(),al&＃61;1<for(int i&＃61;0;iint tc&＃61;1;for(int j&＃61;0;j<(int)Ve[now].size();j&＃43;&＃43;){int k&＃61;Ve[now][j],x&＃61;e[k][0],y&＃61;e[k][1];if((i>>(id[x]-1)&1)^(i>>(id[y]-1)&1))tc&＃61;(ll)tc*((i>>(id[x]-1)&1)?e[k][2]:e[k][3])%mod*2ll%mod;}sum[i]&＃61;sum[i>>1]&＃43;(i&1);add(g[now][sum[i]],tc);}
}
int f[maxn],temp[maxn];int main()
{Inv&＃61;inv(10000);scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){int x,y,w; scanf("%d%d%d",&x,&y,&w);e[i][0]&＃61;x,e[i][1]&＃61;y; w&＃61;(ll)w*Inv%mod;e[i][2]&＃61;w;e[i][3]&＃61;(1-w&＃43;mod)%mod;ins(x,y,i); ins(y,x,i);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) if(!vis[i]){&＃43;&＃43;cnt,dfs(i);Solve(cnt);}f[0]&＃61;1; int nowsum&＃61;0;for(int i&＃61;1;i<&＃61;cnt;i&＃43;&＃43;){for(int j&＃61;0;j<&＃61;nowsum&＃43;(int)V[i].size();j&＃43;&＃43;) temp[j]&＃61;0;for(int j&＃61;0;j<&＃61;nowsum;j&＃43;&＃43;) for(int k&＃61;0;k<&＃61;(int)V[i].size();k&＃43;&＃43;)add(temp[j&＃43;k],(ll)f[j]*g[i][k]%mod);nowsum&＃43;&＃61;(int)V[i].size();for(int j&＃61;0;j<&＃61;nowsum;j&＃43;&＃43;) f[j]&＃61;temp[j];}int ans&＃61;0,inv2&＃61;inv(2);for(int i&＃61;1;i1);ans&＃61;(ll)ans*pw(10000,n*(n-1))%mod;printf("%d\n",ans);return 0;
}