P10674 【MX-S1-T3】电动力学 题解

· · 题解

这题真的只有蓝吗。。。看来是我太菜了

不过我竟然场切了 dp，感到震惊。

这个题首先要选择一个好算的东西计数，如果考虑对每个 S 算 T 的方案就很不好搞，所以反过来，考虑对每个 T 算有多少个 S 满足条件。|T|\leq 1 是平凡的，一下设 |T|\geq 2。

先看树的情况，是显然的，S 中的点必定在 T 中所有点构成的虚树中，且这是充要的，换言之，设 T 中点构成的虚树大小为 m，则共有 2^m 的 S 满足条件。

考虑推广。发现“简单路径”很像点双相关（说句闲话，我比赛以为简单路径指的是边不重复）。于是大胆猜测构成的是所有有 |T| 中路径经过的点双的并集大小。证明是容易的，由点双性质可知。

所以考虑建出圆方树 dp。这时候就需要给圆方树上每个点赋权，使得答案容易计算。发现可以这样赋值：对于圆点，权值为 0，对于方点 x，权值为 s_x-1，s_x 表示第 x 个点双的大小。这样所有有 |T| 中路径经过的点双的并集大小即为所有 T 中的点在圆方树上构成的虚树中的点的权值和加一，设这个玩意为 F(T)。即求 \sum_{T} 2^{F(T)}=2\sum_{T} 2^{F(T)-1}。

考虑 dp，设 f_x 表示虚树根为 x 的方案数。考虑合并子树状态，一定为选择若干个在 x 的不同子树的点，然后对其求和。设 g(y,x) 表示对于 x 为 y 的祖先，x 到 y 路径上的权值和（不包含 y），设 t_x=\sum_{y\in S_x} f_y2^{g(y,x)}，S_x 表示 x 的子树构成的集合，同理定义 T_x 表示 x 所有儿子构成的集合。

这样就做完了，复杂度 \mathcal{O}(n)

细节见代码：

#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
const ll mod=998244353;
il int read(){
    int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-48,c=getchar();
    return x;
}
il void add(ll &x,ll y){x=(x+y>=mod?x+y-mod:x+y);}
const int N=1e6+5;
int n,m,dfn[N],low[N],cnt,st[N],top,bel[N],idx,siz[N];ll ans,pw[N],f[N],s[N],t[N];
vector<int> e[N],g[N];
il void adde(int x,int y,vector<int> e[]){e[x].push_back(y),e[y].push_back(x);}
void tarjan(int x,int fath){
    int y,z;dfn[x]=low[x]=++cnt,st[++top]=x;
    for(int y:e[x]){
        if(y==fath) continue;
        if(!dfn[y]){
            tarjan(y,x),low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                ++idx,adde(idx+n,x,g),bel[x]=idx,siz[idx+n]=1;
                do{
                    z=st[top--],bel[z]=idx,adde(idx+n,z,g),++siz[idx+n];
                }while(z!=y);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
void dfs(int x,int fath){
    if(x>1 && g[x].size()==1){
        f[x]=s[x]=t[x]=1;
        return ;
    }
    ll u=0,v,w=1ll;
    for(int y:g[x]){
        if(y==fath) continue;
        dfs(y,x),add(s[x],s[y]);
    }
    if(x>n){
        for(int y:g[x]){
            if(y==fath) continue;
            add(u,t[y]),w=(w*(1ll+t[y]))%mod,t[x]=(t[x]+pw[siz[x]-1]*t[y])%mod;
        }
        f[x]=((w-1ll-u+mod)*pw[siz[x]-1])%mod;
    }
    else{
        for(int y:g[x]){
            if(y==fath) continue;
            add(u,t[y]),w=(w*(1ll+t[y]))%mod,add(t[x],t[y]);
        }
        f[x]=(u+(w-u+mod)*2ll-1)%mod;
    }
    add(s[x],f[x]),add(t[x],f[x]);
}
int x,y,z;ll u,v,w;
int main(){
    scanf("%d%d",&n,&m);pw[0]=1ll;
    for(int i=1;i<=n;++i) pw[i]=(pw[i-1]*2ll)%mod;
    for(int i=1;i<=m;++i) x=read(),y=read(),adde(x,y,e),adde(y,x,e);
    tarjan(1,0);
    dfs(1,0);
    for(int i=1;i<=n+idx;++i) add(ans,f[i]);
    printf("%lld",(2ll*ans+1ll)%mod);
    return 0;
}