「ALFR Round 3」D 核裂变 题解
Moya_Rao
·
·
题解
可以想到建图，按照 x 数组的释放情况来建一张图，其中 u 指向 v 的边表示每一秒，如果 u 会释放能量，则会释放 1 中子到 v 身上。
可那种自动有中子打击的，怎么办呢？简单，用一个 0 节点连接，就当 0 节点是这个自动的嘛。
不过，每个放射性原子并不是一开始就启动的，如果它还没有启动，那么就不能释放能量，这怎么处理呢？很简单，跑一次洪水填充，把每个节点的启动时间弄出来，就能知道它是什么时候启动的了。至于 0 节点，反正是从它开始跑，它的启动时间就可以被设置成 0 嘛。
但是要特殊处理一个东西：如果 k 过于小，使得某些原子并没有在 k 秒内启动呢？这简单，我选择在一开始赋上一个初值，最后统计答案的时候判断一下即可。
现在就是想如何统计答案了，其实上很简单，可以把答案拆成两部分来算，一部分是题面中所说的 a_i，另一部分就是题面中所说的 b。
那个什么 a_i 很好算，利用自己的启动时间算出自己会在这 k 秒内活跃多久，拿这个时间乘上 a_i 即可。
这两个玩意儿，说是说分开算，其实也不然，可以放在一个大的循环里，遍历 $i$ 从 $1$ 到 $n$，每个每个去算就行了。
$0$ 呢？$0$ 也连向了一些点，这些点是无法在刚刚所说的那个循环里计算到的，没什么，多加一个关于 $0$ 的小循环就可以了，看看 $0$ 连向了哪些边，一开始就给它加进去，没什么大碍。
这下，就可以在 $O(n+m)$ 左右的时间内完成，非常快速。不过，千万千万要记得，对 $998244353$ 取模！还有就是，最好写一下快读，否则可能会大大降低其效率！
这里给出一份参考代码，赛时敲的，能 AC，别怀疑。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
const long long mod = 998244353;
long long n,k,m,a[N],t[N],ans[N];
vector<int> g[N];
queue<int> q;
long long read(){
long long su=0,pp=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')pp=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
su=su*10+ch-'0';
ch=getchar();
}
return su*pp;
}
int main(){
n=read(),k=read(),m=read();
for(int i=1;i<=m;i++)g[0].push_back(read());
for(int i=1;i<=n;i++){
a[i]=read(),t[i]=k+1;
for(int j=1;j<=a[i];j++)g[i].push_back(read());
}
q.push(0);
while(!q.empty()){
int u=q.front();q.pop();
if(t[u]==k)break;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(t[v]<=k)continue;
t[v]=t[u]+1;q.push(v);
}
}
for(int i=0;i<g[0].size();i++){
int u=g[0][i];
ans[u]+=k%mod;ans[u]%=mod;
}
for(int i=1;i<=n;i++){
if(t[i]==k+1)continue;
ans[i]+=(((k-t[i]+1)%mod)*a[i])%mod;ans[i]%=mod;
for(int j=0;j<g[i].size();j++){
int u=g[i][j];
ans[u]+=(k-t[i])%mod;ans[u]%=mod;
}
}
for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
return 0;
}
```
如果本篇题解对你有所帮助，请留下一个小小的赞，谢谢！