为什么谷歌网站打不开,制作小动画的软件,服务外包和劳务外包区别,做财税的网站有哪些题意#xff1a;nnn 个点 mmm 条边的连通无向图的独立集个数模 998244353998244353998244353。 n≤105,m≤n10n\leq 10^5,m\leq n10n≤105,m≤n10
为什么标题要把两个算法写一起#xff1f;因为这两个东西在这类问题上是本质相同的#xff0c;这也是写这篇博客的原因。
显…题意nnn 个点 mmm 条边的连通无向图的独立集个数模 998244353998244353998244353。
n≤105,m≤n10n\leq 10^5,m\leq n10n≤105,m≤n10
为什么标题要把两个算法写一起因为这两个东西在这类问题上是本质相同的这也是写这篇博客的原因。
显然是随便找棵树出来 dp然后枚举非树边容斥。
设 dp(u,0/1)dp(u,0/1)dp(u,0/1) 表示考虑 uuu 的子树uuu 不选/选的方案
dp(u,0)∏v∈son(u)(dp(v,0)dp(v,1))dp(u,0)\prod_{v\in son(u)}(dp(v,0)dp(v,1))dp(u,0)v∈son(u)∏(dp(v,0)dp(v,1))
dp(u,1)∏v∈son(u)dp(v,0)dp(u,1)\prod_{v\in son(u)}dp(v,0)dp(u,1)v∈son(u)∏dp(v,0)
用动态 dp 维护就可以了。但修改操作是乘 000 和撤销乘 000你需要记录乘的 000 的个数不是很好搞。这里介绍等价的虚树的做法。
考虑加入一个儿子 vvv写成矩阵的形式
[dp′(u,0)dp′(u,1)][dp(v,0)dp(v,1)00dp(v,0)][dp(u,0)dp(u,1)]\left[ \begin{matrix} dp(u,0) \\ dp(u,1) \end{matrix}\right] \left[ \begin{matrix} dp(v,0)dp(v,1) 0\\ 0dp(v,0) \end{matrix} \right] \left[ \begin{matrix} dp(u,0)\\ dp(u,1) \end{matrix} \right] [dp′(u,0)dp′(u,1)][dp(v,0)dp(v,1)00dp(v,0)][dp(u,0)dp(u,1)]
这其实可以不用矩阵直接算出来。
因为有关于关键点的修改我们希望维护这些信息来快速得到需要的 dp 值。所以我们建出关键点的虚树维护虚树上每条边的转移系数。因为儿子的信息是不确定的或者说是动态的并且中途有加的操作所以这里必须用矩阵。
对于这条边对应的原树路径每向上走一步 [dp(u,0)dp(u,1)]T\left[\begin{matrix}dp(u,0)dp(u,1)\end{matrix}\right]^T[dp(u,0)dp(u,1)]T 产生的贡献就会变成 [dp(u,0)dp(u,1)dp(u,0)]T\left[\begin{matrix}dp(u,0)dp(u,1)dp(u,0)\end{matrix}\right]^T[dp(u,0)dp(u,1)dp(u,0)]T 对应转移矩阵为
S[1110]S\left[\begin{matrix}11\\10\end{matrix}\right]S[1110]
然后每走一步再加上不在虚树上的儿子的贡献。
设得到的转移矩阵为 trans(u)trans(u)trans(u)每次更新的答案为 ans(u)ans(u)ans(u) 那么
ans(u)f(u)∏(u,v)∈VirtualTreetrans(v)ans(v)ans(u)f(u)\prod_{(u,v)\in VirtualTree}trans(v)ans(v)ans(u)f(u)(u,v)∈VirtualTree∏trans(v)ans(v)
其中 f(u)f(u)f(u) 为 uuu 的不在虚树上的儿子的贡献。
开始听信题解区 O(n)\Omicron(n)O(n) 建虚树挂了怎么都调不出来然后极度愤怒的情况下换成 O(klogk)\Omicron(k\log k)O(klogk) 就过了……这个故事告诉我们考场上不要自己 yy 奇怪的算法。
#include iostream
#include cstdio
#include cstring
#include cctype
#include utility
#include algorithm
#include vector
#define MAXN 100005
#define MAXM 200005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
const int MOD998244353;
inline int add(const int x,const int y){return xyMOD? xy-MOD:xy;}
inline int dec(const int x,const int y){return xy? x-yMOD:x-y;}
typedef long long ll;
inline int qpow(int a,int p)
{int ans1;while (p){if (p1) ans(ll)ans*a%MOD;a(ll)a*a%MOD,p1;}return ans;
}
#define inv(x) qpow(x,MOD-2)
struct mat
{int e[2][2];inline mat(const int v0){e[0][0]e[1][1]v,e[0][1]e[1][0]0;}inline int* operator [](const int i){return e[i];}inline const int* operator [](const int i)const{return e[i];}
};
mat S;
inline mat operator *(const mat a,const mat b)
{mat c;for (int i0;i2;i)for (int k0;k2;k)for (int j0;j2;j)c[i][j](c[i][j](ll)a[i][k]*b[k][j])%MOD;return c;
}
typedef pairint,int pi;
vectorint e[MAXN];
vectorpi ex;
int dep[MAXN],fa[MAXN][20],siz[MAXN],key[MAXN],dfn[MAXN],tim;
int F[MAXN][2];
void dfs(int u,int f)
{dfn[u]tim,dep[u]dep[fa[u][0]f]1;for (int i1;i20;i) fa[u][i]fa[fa[u][i-1]][i-1];F[u][0]F[u][1]1;for (int i0;i(int)e[u].size();i)if (e[u][i]!f){if (dfn[e[u][i]]) {if (dfn[e[u][i]]dfn[u]) continue;ex.push_back(make_pair(u,e[u][i]));e[u][i]f;continue;}dfs(e[u][i],u);F[u][0](ll)add(F[e[u][i]][0],F[e[u][i]][1])*F[u][0]%MOD;F[u][1](ll)F[e[u][i]][0]*F[u][1]%MOD;}
}
inline int lca(int x,int y)
{if (dep[x]dep[y]) swap(x,y);int tdep[x]-dep[y];for (int i0;(1i)t;i) if (t(1i)) xfa[x][i];if (xy) return x;for (int i19;i0;i--)if (fa[x][i]!fa[y][i])xfa[x][i],yfa[y][i];return fa[x][0];
}
mat dp[MAXN];
vectorint lis,son[MAXN];
int col[MAXN],tmp[MAXN][2];
inline bool cmp(const int x,const int y){return dfn[x]dfn[y];}
const int Rt1;
int main()
{S[0][0]S[0][1]S[1][0]1;int n,m;nread(),mread();for (int i1;im;i){int u,v;uread(),vread();e[u].push_back(v),e[v].push_back(u);}dfs(Rt,0);for (int i0;i(int)ex.size();i) lis.push_back(ex[i].first),lis.push_back(ex[i].second);lis.push_back(Rt);sort(lis.begin(),lis.end(),cmp);int s(int)lis.size(); for (int i0;is-1;i) lis.push_back(lca(lis[i],lis[i1]));sort(lis.begin(),lis.end(),cmp);lis.erase(unique(lis.begin(),lis.end()),lis.end()); for (int i0;i(int)lis.size();i) key[lis[i]]1;for (int i0;i(int)lis.size();i) for (int ulis[i];u;siz[u],ufa[u][0]);for (int T0;T(int)lis.size();T){mat curmat(1);for (int vlis[T],ufa[v][0];u;vu,ufa[u][0]){if (key[u]){son[u].push_back(lis[T]);dp[lis[T]]cur;break;}curS*cur;for (int i0;i(int)e[u].size();i)if (!siz[e[u][i]]e[u][i]!fa[u][0]){int aadd(F[e[u][i]][0],F[e[u][i]][1]),bF[e[u][i]][0];cur[0][0](ll)cur[0][0]*a%MOD,cur[0][1](ll)cur[0][1]*a%MOD;cur[1][0](ll)cur[1][0]*b%MOD,cur[1][1](ll)cur[1][1]*b%MOD;}}}for (int t0;t(int)lis.size();t){int ulis[t];F[u][0]F[u][1]1;for (int i0;i(int)e[u].size();i)if (!siz[e[u][i]]e[u][i]!fa[u][0]){F[u][0](ll)add(F[e[u][i]][0],F[e[u][i]][1])*F[u][0]%MOD;F[u][1](ll)F[e[u][i]][0]*F[u][1]%MOD;}}int k(int)ex.size();int ans0;
// for (int i0;ik;i) printf(%d %d\n,ex[i].first,ex[i].second);
// for (int i1;in;i) printf(%d %d\n,F[i][0],F[i][1]);for (int S0;S(1k);S){int w0;for (int i0;ik;i) col[ex[i].first]col[ex[i].second]0;for (int i0;ik;i) if (S(1i)) col[ex[i].first]col[ex[i].second]1,w^1;for (int T(int)lis.size()-1;T0;T--){int ulis[T];tmp[u][0]F[u][0],tmp[u][1]F[u][1];for (int i0;i(int)son[u].size();i){tmp[u][0](ll)add(tmp[son[u][i]][0],tmp[son[u][i]][1])*tmp[u][0]%MOD;tmp[u][1](ll)tmp[son[u][i]][0]*tmp[u][1]%MOD;}if (col[u]) tmp[u][0]0;if (u!Rt){mat t;t[0][0]tmp[u][0],t[1][0]tmp[u][1];tdp[u]*t;tmp[u][0]t[0][0],tmp[u][1]t[1][0];}}int tadd(tmp[Rt][0],tmp[Rt][1]);if (w) ansdec(ans,t);else ansadd(ans,t);
// printf(%d\n,t);}coutans;return 0;
}
