题解 P4426 【[HNOI/AHOI2018]毒瘤】

大家好我非常喜欢硬核数据结构，所以敲了个动态dp过了这题 可能常数有点丢人(其实就是树的点会跑200来ms)然后代码量似乎和很多人差不多？(4k左右) 这里强烈安利一下全局平衡二叉树这个动态dp的实现方式，这个算法有一个好处就是常数真的小，所以就算你胡乱实现也能过题(尽管这东西通常不是标算但是1e5内卡不住)比如今年noip的d2t3也能拿这个算法过掉(尽管并敲不出来) ________________________ ### 前置知识：动态dp 不会这东西的可以出门左转你站模板区去学习一下 没准树剖也能过这题？ ## 本题题解 题目意思简单易懂，给你一张连通图，求独立集的方案数，保证非树边最多11条 那么我们先不管非树边做一遍树形dp，设$dp(u,0/1)$表示当u选取或者不选取的时候,u的子树中的独立集方案数 那么转移方程当然十分的显然了，假设我们正在合并一条树边$(u,v)$并且u是v的父亲 $$dp(u,0)=dp(u,0)(dp(v,0)+dp(v,1))$$ $$dp(u,1)=dp(u,1)dp(v,0)$$ 那么此时显然我们计数记多了，发现独立集限制(也就是非树边)最多有11条，因此我们可以$O(2^{11})$枚举一下到底打破了哪几个限制，然后用至少打破0个限制-至少打破1个限制+至少打破2个限制-至少打破3个限制....如此这般的容斥下来我们就可以得到答案了 假设我们已经钦定了一些非树边现在我们要全部打破这些限制 那这个操作实在是容易，钦定这些树边的端点全部出现在独立集中就行了，(而且似乎你也只能这么做) 接下来如果我们每次暴力跑个树形dp似乎复杂度有些捉急$O(2^{11}n)$ 肯定是tle的 那么我们怎么办呢？ 当然是动态dp大法啦~ 来来来让我们把dp的转移写成轻重链剖分之后矩阵dp的形式 记 $$ldp(u,0)=\prod_{v \in u.lightson}dp(v,0)+dp(v,1)$$ $$ldp(u,1)=\prod_{v \in u.lightson}dp(v,0)$$ 记$dp(i,0/1)$表示一条重链按照深度排序之后的第i大的点的dp值 则我们有 $$\begin{bmatrix} dp_{i-1,0} \\ dp_{i-1,1} \end{bmatrix} × \begin{bmatrix} ldp_{i,0} & ldp_{i,1} \\ ldp_{i,0} & 0 \end{bmatrix}=\begin{bmatrix} dp_{i,0} \\ dp_{i,1} \end{bmatrix}$$ 这里的两个列向量其实是行向量，我主要是因为这样看起来比较爽才敲成这样的 那么我们采用全局平衡二叉树维护一下每条重链的矩阵连乘积就做完这题了？ 不你忽略了一个问题……,在你跳跃全局平衡二叉树上的一条轻边的时候你需要在$ldp(fa(p),0/1)$中删掉$dp(p,0/1)$的值，换句话讲就是做除法,而显然这东西在$dp(p,0/1)$是0的时候是除不掉的…… 那么怎么办呢？我们对于每一个$ldp(u,0/1)$如果他的值是0就额外记一下到底有几个0乘到了里面，这样我们就可以做除法了（因为我们只是想要删除一个值而不是真的做除法） 这样你就可以愉快的处理除0的问题了然后我们就可以大力的动态dp过了这题 只是需要注意一点朴素的枚举集合加动态dp的复杂度是$O(11×2^{11}log^2n+nlogn)$的可能常数不优秀就tle了…… 没关系我们把枚举集合换成dfs然后这样的话我们总的修改量就是$O(2^{11})$级别的,然后这题简直随便过 如果你觉得撤销操作难写的话可以像我一样每个节点开一个栈专门用来回撤 然后这题就愉快的做完了~ 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> using namespace std;const int N=1e5+10;typedef long long ll;const ll mod=998244353; inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;} struct nod//用来做除法的结构体 { ll v1;int c1;ll v2;int c2; inline void ins(const ll& t1,const ll& t2) {(v1*=(t1)?t1:1)%=mod;c1+=(t1==0);(v2*=(t2)?t2:1)%=mod;c2+=(t2==0);} inline void del(const ll& t1,const ll& t2) { (v1*=(t1)?po(t1,mod-2):1)%=mod;c1-=(t1==0); (v2*=(t2)?po(t2,mod-2):1)%=mod;c2-=(t2==0); } }; struct mar//矩阵 { ll mp[2][2]; inline ll* operator [](const int& x){return mp[x];} friend mar operator *(mar a,mar b) { mar c; c[0][0]=((ll)a[0][0]*b[0][0]+(ll)a[0][1]*b[1][0])%mod; c[0][1]=((ll)a[0][0]*b[0][1]+(ll)a[0][1]*b[1][1])%mod; c[1][0]=((ll)a[1][0]*b[0][0]+(ll)a[1][1]*b[1][0])%mod; c[1][1]=((ll)a[1][0]*b[0][1]+(ll)a[1][1]*b[1][1])%mod;return c; } void operator =(const nod& b) {mp[1][0]=mp[0][0]=(b.c1)?0:b.v1;mp[0][1]=(b.c2)?0:b.v2;} }; int v[2*N];int x[2*N];int ct;int al[N];int n;int m;ll ans; int eu[22];int ev[22];int hd;int siz[N];int h[N];int mi[N]; inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;} struct bcj//智商不够数据结构来凑，随手敲了个并查集判非树边 { int fa[N]; inline int f(int x){return fa[x]=(x==fa[x])?x:f(fa[x]);} inline void u(int x,int y){fa[f(x)]=f(y);} inline void ih(){for(int i=1;i<=n;i++)fa[i]=i;} inline void ins(int U,int V) {if(f(U)==f(V))eu[++hd]=U,ev[hd]=V;else add(U,V),add(V,U),u(U,V);} }ufs; inline int dfs1(int u,int f)//轻重链剖分 { for(int i=al[u];i;i=x[i]) if(v[i]!=f)siz[u]+=dfs1(v[i],u),h[u]=(siz[h[u]]<siz[v[i]])?v[i]:h[u];return ++siz[u]; } struct global_biased_tree//全局平衡二叉树 { mar mul_bas[N][22];mar we_bas[N][22];nod ld_bas[N][22];int s[N][2]; mar* nmul[N];mar* nwe[N];nod* nld[N];//为了写的爽每个点开了个指针模拟栈 int st[N];int tp;int wsiz[N];int rot;int fa[N];//define n连实现栈 # define mul(p) (*nmul[p]) # define we(p) (*nwe[p]) # define incm(p) (*(nmul[p]+1)=*nmul[p],++nmul[p]) # define decm(p) (--nmul[p]) # define incw(p) (*(nwe[p]+1)=*nwe[p],++nwe[p]) # define decw(p) (--nwe[p]) # define ld(p) (*nld[p]) # define incl(p) (*(nld[p]+1)=*nld[p],++nld[p]) # define decl(p) (--nld[p]) inline void ud(int p){mul(p)=mul(s[p][0])*we(p)*mul(s[p][1]);}//更新 inline void ih()//初始化指针 { for(int i=0;i<=n;i++)nmul[i]=mul_bas[i];for(int i=0;i<=n;i++)nwe[i]=we_bas[i]; for(int i=0;i<=n;i++)nld[i]=ld_bas[i]; for(int i=0;i<=21;i++)mul_bas[0][i][0][0]=1,mul_bas[0][i][1][1]=1; } inline int sbuild(int l,int r)//每条重链建bst { if(l>r)return 0; int mid=l;int sum=0;for(int i=l;i<=r;i++)sum+=wsiz[st[i]]; for(int pre=0;(pre<<1)<sum;mid++)pre+=wsiz[st[mid]];mid--; s[st[mid]][0]=sbuild(l,mid-1);fa[s[st[mid]][0]]=st[mid]; s[st[mid]][1]=sbuild(mid+1,r);fa[s[st[mid]][1]]=st[mid];ud(st[mid]); return st[mid]; } inline int solve(int u,int f)//链分治 { for(int p=u,nf=f;p;nf=p,p=h[p]) { wsiz[p]++;ld(p).v1++;ld(p).v2++; for(int j=al[p];j;j=x[j]) if(v[j]!=h[p]&&v[j]!=nf) { int ve=solve(v[j],p);fa[ve]=p;wsiz[p]+=siz[v[j]]; ld(p).ins((mul(ve)[0][0]+mul(ve)[0][1])%mod,mul(ve)[0][0]); }we(p)=ld(p); }tp=0;for(int p=u;p;p=h[p])st[++tp]=p;reverse(st+1,st+tp+1);return sbuild(1,tp); } inline void modify(int u)//修改 { incw(u);incl(u);ld(u).v1=0;we(u)=ld(u); for(int p=u;p;p=fa[p]) if(fa[p]&&s[fa[p]][0]!=p&&s[fa[p]][1]!=p) { int f=fa[p];incw(f);incl(f); ld(f).del((mul(p)[0][0]+mul(p)[0][1])%mod,mul(p)[0][0]);incm(p),ud(p); ld(f).ins((mul(p)[0][0]+mul(p)[0][1])%mod,mul(p)[0][0]);we(f)=ld(f); }else incm(p),ud(p); } inline void undo(int u)//撤销 { decw(u);decl(u); for(int p=u;p;p=fa[p]) if(fa[p]&&s[fa[p]][0]!=p&&s[fa[p]][1]!=p)decw(fa[p]),decl(fa[p]),decm(p); else decm(p); } inline ll calc(){return (mul(rot)[0][0]+mul(rot)[0][1])%mod;} }gbt; inline void dfs(int stp,int siz)//dfs+容斥 { if(stp==hd+1) { if(siz&1)(ans+=mod-gbt.calc())%=mod; else (ans+=gbt.calc())%=mod;return; }dfs(stp+1,siz); if(!mi[eu[stp]]){mi[eu[stp]]=stp;gbt.modify(eu[stp]);} if(!mi[ev[stp]]){mi[ev[stp]]=stp;gbt.modify(ev[stp]);} dfs(stp+1,siz+1); if(mi[ev[stp]]==stp){mi[ev[stp]]=0;gbt.undo(ev[stp]);} if(mi[eu[stp]]==stp){mi[eu[stp]]=0;gbt.undo(eu[stp]);} } int main() { scanf("%d%d",&n,&m);ufs.ih(); for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),ufs.ins(u,v);dfs1(1,0); gbt.ih();gbt.rot=gbt.solve(1,0);dfs(1,0);printf("%lld",ans);return 0;//拜拜程序~ } ```