好题喵。
题目链接。
题意
给定一张简单连通无向图，每一条边每一个时刻有 的概率出现。初始的时候节点 有一条消息。
对于一个没有消息的点 ，若某一个现在与 相邻的点在上一时刻有消息，则点 这一时刻会获得消息。
。。
题解
设 表示，恰好只有
内部节点有消息，这个状态有多少的概率会经过。
设 表示若恰好只有
这些点有消息，经过多少个时刻之后，会有新的节点接受到消息。
那么答案就是 。
那么 很容易 算出来，只需要看一下 向外连的边即可。
设 表示当前状态是 ，经过一个时刻，新增了
这些点获得信息的概率。
考虑
怎么转移，枚举下一次有新增的点的时候，新增的点集合为 。
那么就有转移 。
精细实现一下就能做到 。
听说这个能过，真的假的
设 ，和 即全集。
考虑 向 的转移，此时只需要下个时刻
向
的点里面没有连边即可。
那么设
表示经过一个时刻， 这些点没有获得信息的概率，即要求 和 没有边。
就有转移 。
考虑 这种东西如何表示，设
表示 。
考虑能不能只用
这种东西把 表示出来。
那么推一下能发现 。
往回带，就能得到转移式 。
减号后面只和 有关，而减号前面
都有
对于后面的部分，可以看出，这是一个半在线子集卷积，首先尝试回忆普通的子集卷积。
两个序列 的子集卷积满足
。
那么我们把 都按照 进行分类。
具体的，令 。 同理。
那么将序列 与 做或卷积，得到的序列中 的部分就是
的部分。
直接做，需要跑
次或卷积，复杂度是 。
考虑优化 FMT 的次数，
的正 FMT 可以提前预处理好，复杂度是 。
卷完以后还需要进行逆变化，直接把所有 相同的放一起逆变换，复杂度是 。
这样就在
复杂度内完成了普通的子集卷积。
那么再考虑这种半在线的子集卷积呢，能发现，还是可以参照上面的过程。
假设我们当前需要计算
的半在线卷积。
考虑从小到大枚举数字 。那么我们先计算 的或卷积正变化结果。
令 ，其中 为序列按位乘。
这样就做完了半在线的子集卷积，半在线的或卷积也同理。
这样就得到了 的 ，进而能得到 。
复杂度 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=998244353;
const int N=2097152;
ll P[N];
ll Q[N];
ll f[N];
ll g[N];
ll a[22][N];
ll b[22][N];
ll C[N];
ll D[N];
ll E[N];
int num[N];
int n,m;
inline ll qow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
inline void Add(ll &a,ll b){ a+=b;if(a>=mod) a-=mod;}
inline void FMT(ll *f,int s=0)
{
for(int i=s;i<n;i++) for(int j=s|(1<<i);j<(1<<n);j=(j+(1<<s))|(1<<i)) Add(f[j],f[j^(1<<i)]);
}
inline void IFMT(ll *f)
{
for(int i=1;i<n;i++) for(int j=(1<<i)+1;j<(1<<n);j=(j+2)|(1<<i)) Add(f[j],mod-f[j^(1<<i)]);
}
int main()
{
n=read(),m=read();int U=(1<<n)-1;
for(int i=0;i<(1<<n);i++) P[i]=Q[i]=1,num[i]=__builtin_popcount(i);
for(int i=1;i<=m;i++)
{
int u=read()-1,v=read()-1,p=read(),q=read();
ll w=p*qow(q,mod-2)%mod;w=(1-w+mod)%mod;
int id=(1<<u)|(1<<v);
P[id]=P[id]*w%mod;
Q[1<<u]=Q[1<<u]*w%mod;
Q[1<<v]=Q[1<<v]*w%mod;
Q[id]=Q[id]*qow(w*w%mod,mod-2)%mod;
}
for(int i=0;i<n;i++) for(int j=(1<<i);j<(1<<n);j=(j+1)|(1<<i)) if(j&(1<<i))
{
P[j]=P[j]*P[j^(1<<i)]%mod;
Q[j]=Q[j]*Q[j^(1<<i)]%mod;
}
f[1]=1;
for(int k=1;k<n;k++)
{
for(int i=1;i<(1<<n);i+=2) if(num[i]==k)
{
ll V=f[i]*qow(mod+1-Q[i],mod-2)%mod;
D[i]=V*Q[i]%mod;
if(i>1) D[i]=(D[i]+f[i])%mod;
a[k][i]=V*qow(P[i],mod-2)%mod;
}
for(int i=0;i<(1<<n);i+=2) if(num[i]==k) b[k][i]=P[i^U];
memcpy(E,D,sizeof(D));
FMT(E,1),FMT(a[k],1),FMT(b[k]);
memset(C,0,sizeof(C));
for(int i=1;i<=k;i++) for(int j=1;j<(1<<n);j+=2) C[j]=(C[j]+a[i][j]*b[k+1-i][j])%mod;
IFMT(C);
for(int i=1;i<(1<<n);i+=2) if(num[i]==k+1)
{
f[i]=C[i]*qow(P[U^i],mod-2)%mod;
f[i]=(f[i]-E[i]+mod)%mod;
}
}
ll ans=0;
for(int i=1;i<U;i+=2)
{
g[i]=qow((mod+1-Q[i])%mod,mod-2);
ans=(ans+f[i]*g[i])%mod;
}
ans=(ans%mod+mod)%mod;
printf("%lld\n",ans);
return 0;
}
|
感谢观看！