额，虽然这道题在你谷上的评分是蓝，但我觉得并不简单。
顺便让我复习了一下暑假讲过的知识点。
题目链接
题意
现在一共有 个人，其中第 个人有
个朋友，并且朋友关系是单向的。（即可能存在两个人A、B，使得 A 是 B
的朋友，但是 B 不是 A 的朋友）
现在有一场派对，持续若干天。第
天时，第 个人有 的概率参加派对，有 的概率不参加派对。
对于第 天来说，第
个人参加派对，当且仅当存在至少一个 的朋友 ，使得第 个人在第 天参加了派对。
求第
天时，参加派对的期望人数，对 取模。
题解
首先来考虑
的时候怎么做。
显然对于任何一个人 ，只要他有一个朋友在第 天时参加派对， 就会去参加派对。
这个时候我们可以直接算出
不参加派对的概率，从而算出
参加派对的概率。
现在来考虑 。
显然对于任何一个人 ，只要存在一个人 在第 天参加派对，并且 是 朋友的朋友， 就会去参加派对。
显然，这种“朋友套朋友”的关系不好叙述，我们换一种方式。
我们把一个人看作一个点，如果人
是人 的朋友，我们再连一条 的边。
这样子朋友的关系就很好叙述了。
对于 ，也就是对于每一个 ，只要存在一个人 在第 天参加派对，并且从 经过恰好两条边可以到达点 ，
就会去参加派对。
如果
为任意数，那么对于任何一个人 ，只要存在一个人 在第 天参加派对，并且从 经过恰好 条边可以到达点 ，
就回去参加派对。
现在如果我们对于每一个人 ，如果能求出所有的人 ，那么这个问题就解决了。
这个问题显然可以使用倍增 Floyd 来解决，我们设 表示第 个人走 条边，是否可以走到 ，转移的时候枚举中间点即可。
这样时间复杂度是 ，离满分还差一点。
这个时候我们能发现，对于每一个 ，它的值不是 就是 （废话。
所以我们可以使用bitset进行优化。
也就是说我们开若干个 bitset，其中 表示的是第 个人走 条边，走到的人的集合。
时间复杂度是 ，能过。
代码
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
| #include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<bitset>
#include<queue>
#include<map>
#define inf 0x3f3f3f3f3f3f3f3fll
const int mod=998244353;
using namespace std;
using ll=long long;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
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;
}
bitset<501>f[501][31];
bitset<501>num[501];
bitset<501>mem[501];
bool vis[501][501];
int p[501];
int n,m;
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
{
p[i]=read(),num[i][i]=1;int c=read();
for(int j=1;j<=c;j++) f[i][0][read()]=1;
}
for(int i=1;i<=30;i++) for(int u=1;u<=n;u++) for(int v=1;v<=n;v++)
if(f[u][i-1][v]) f[u][i]|=f[v][i-1];
for(int i=0;i<=30;i++) if(m&(1<<i))
{
for(int u=1;u<=n;u++) mem[u]=num[u],num[u].reset();
for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) if(mem[u][v]==1)
num[u]|=f[v][i];
}
ll ans=0;
for(int i=1;i<=n;i++)
{
ll val=1;
for(int j=1;j<=n;j++) if(num[i][j]==1) val=val*(mod+1-p[j])%mod;
ans+=mod+1-val;
}
printf("%lld\n",ans%mod);
return 0;
}
|
感谢观看。