<span>省选模拟6 题解</span>

首先考虑怎样的情况答案是不收敛的。

操作中涉及到对一个权值非$0$，并且不作除法的点的加法贡献。

因为只要最终的答案，可以想到对每个点作为出边的贡献分别处理。

部分分提示求出第一次迭代的贡献，发现对于每个点，贡献都是一个等比数列，所以只要代入求和公式就好了。

然而暴力做的复杂度是$O(mk)$的，会被菊花图的数据卡掉。

考虑如何优化这个东西，根据套路我们将点按照度数分块。

定义度数大于$\sqrt m$的点为重点，度数小于等于$\sqrt m$的点为轻点。

分别讨论：

对于对轻点的操作，因为度数并不大，可以直接暴力。

对于重点的重出边，因为重点个数并不多，可以直接暴力。

对于重点的轻出边，考虑打标记表示这个重点到连接的所有轻点进行了更新操作，修改轻点之前（以及所有操作进行完之后）需要扫重点以累计这个答案。

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int mod=998244353;
 5 const int N=2e5+7;
 6 const int inv2=499122177;
 7 int n,m,k,tot;
 8 bool vis[N];
 9 int s[N],head[N],nxt[N],to[N],d[N],sz[N],flag[N];
10 ll sum[N],tim[N],w[N],t[N];
11 inline void add(int a,int b){
12     nxt[++tot]=head[a]; to[head[a]=tot]=b;
13     nxt[++tot]=head[b]; to[head[b]=tot]=a;
14     ++d[a]; ++d[b];
15 }
16 inline ll qpow(ll x,int k,ll r=1){
17     for(;k;k>>=1,x=x*x%mod) if(k&1) r=r*x%mod;
18     return r;
19 }
20 vector<int> g[N];//与i临接的重点
21 inline int read(register int x=0,register char ch=getchar(),register int f=0){
22     for(;!isdigit(ch);ch=getchar()) f=ch=='-';
23     for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
24     return f?-x:x;
25 }
26 int main(){
27     while(scanf("%d%d%d",&n,&m,&k)==3){
28         const int sq=sqrt(n)+1; tot=0;
29         memset(vis,0,sizeof(vis));
30         memset(head,0,sizeof(head));
31         memset(d,0,sizeof(d));
32         memset(sz,0,sizeof(sz));
33         memset(flag,0,sizeof(flag));
34         memset(sum,0,sizeof(sum));
35         for(int i=1;i<=n;++i) t[i]=w[i]=read(),tim[i]=1,g[i].clear();
36         for(int i=1;i<=k;++i) s[i]=read();
37         for(int i=1;i<=m;++i) add(read(),read());
38         for(int i=1;i<=n;++i) if(d[i]>=sq) vis[i]=1;
39         for(int i=1;i<=n;++i) for(int j=head[i];j;j=nxt[j]) if(vis[to[j]]) g[i].push_back(to[j]);
40         for(int o=1;o<=k;++o){
41             int x=s[o];
42             if(vis[x]){
43                 for(auto to:g[x]) sum[to]+=t[to];
44                 ++flag[x];
45                 tim[x]=tim[x]*inv2%mod;
46                 t[x]=t[x]*inv2%mod;
47             }
48             else{
49                 for(int i=head[x];i;i=nxt[i]){
50                     if(vis[to[i]]&&sz[i]<flag[to[i]]) sum[x]+=t[x]*(flag[to[i]]-sz[i]),sz[i]=flag[to[i]];
51                     sum[to[i]]+=t[to[i]];
52                 }
53                 tim[x]=tim[x]*inv2%mod;
54                 t[x]=t[x]*inv2%mod;
55             }
56         }
57         for(int x=1;x<=n;++x) if(!vis[x]) for(int i=head[x];i;i=nxt[i]) if(vis[to[i]]&&sz[i]<flag[to[i]]) sum[x]+=t[x]*(flag[to[i]]-sz[i]),sz[i]=flag[to[i]];
58         ll ans=0; int fl=0;
59         for(int i=1;i<=n;++i) if(sum[i]){
60             sum[i]%=mod;
61             if(tim[i]==1){ fl=1; break; }
62             ans+=sum[i]*qpow(1-tim[i]+mod,mod-2)%mod;
63         }
64         if(fl) puts("-1");
65         else printf("%lld\n",ans%mod);
66     }
67     return 0;
68 }

Yist

因为看到了出现次数，所以想SAM。

在后面加字符对应着$trans$转移，在前面加字符则对应着向$parent$树上的儿子节点转移。

每个时刻实际上只关注当前的串与那些串能够匹配，而并不是具体的串的情况。

所以设$dp_{x,i}$表示SAM上节点$x$，长度为$i$时的最优策略，然而这个状态数为本质不同的字符串个数，随机数据都过不去。

<span>省选模拟6 题解</span>

A. Yist

B. Ernd

C. Sanrd

全站热榜