Legend
给定 (n) 个点的树加上不超过 (11) 条边 ((n le m le n+10))，求独立集数量模 (998244353)。
Link ( extrm{to LOJ})。
Editorial
显然，求独立集数量是一个经典 dp，现在只加上了少量的边，不妨考虑容斥。
设 (f(i)) 表示钦定 (i) 条非树边两个端点都被选的方案，则原问题答案为：
(sum_{i=0}^{m-n+1}(-1)^i f(i))。
由于涉及到【强制选点】，【多次询问 dp 值】的操作，不难想到动态dp。
用树链剖分维护转移矩阵，其转移矩阵应当为：
[egin{bmatrix}
A & A \
B & 0
end{bmatrix}
imes
egin{bmatrix}
varnothing & dp_{i,0} \
varnothing & dp_{i,1}
end{bmatrix}
=
egin{bmatrix}
varnothing & dp_{fa_i,0} \
varnothing & dp_{fa_i,1}
end{bmatrix} \
其中 A = prod_{iin fa_i ext{的轻子树}}(dp_{i,0}+dp_{i,1}) \
B=prod_{iin fa_i ext{的轻子树}}dp_{i,0}
]
钦定一个点必须被选择时，我们只需要把它的转移矩阵内的 (A) 强制赋值为 (0) 即可。
原本我以为这样就可以完成这道题目，但 waaitg 告诉我：你乘积里出现 (0) 的时候，修改 (A,B) 时没有办法通过求逆元的方法撤回。显然，想要构造一组数据使得某个子树的 (dp) 值为 (0) 是非常简单的。于是这个做法就被 HACK 了。
不过自然有一种补救做法，就是对于 (0) 并不乘进去，而是记录一下 (0) 的数量，判断一下当前真实值是 (0) 还是保存的结果。
不过还有一个事情，如果我们枚举每一个集合的时候，都强制选完一些点，然后又撤销，岂不是复杂度很高？(O(11 imes 2^{11} log^2 n imes 2^3)approx 52084736) 虽然可以过了
解决办法就是采用格雷码的形式枚举集合，这样每次只需要删除或加入一个节点。复杂度优化到了 (O(2^{11}log^2 n imes 2^3)approx 4734976)。
不过好像你 dfs 枚举集合复杂度跟格雷码一样诶
不过格雷码常数小一点啦
总复杂度 (O(na^3 + 2^{m-n+1} imes a^3 log^2 n))。其中 (a) 是转移矩阵大小。
Code
巨长无比，好久没有写过这么长的代码了。
#include <bits/stdc++.h>
#define debug(...) ;//fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)
freopen(#x".in" ,"r" ,stdin);
freopen(#x".out" ,"w" ,stdout)
#define LL long long
const int MX = 1e5 + 23;
const LL MOD = 998244353;
int gray(int x){return x ^ (x >> 1);}
int lg2(int x){int i = -1; while(x) x >>= 1 ,++i; return i;}
int bitcnt(int x){return x ? bitcnt(x - (x & -x)) + 1 : 0;}
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
LL qpow(LL a ,LL b ,LL p = MOD){
LL ans = 1;
while(b){if(b & 1) ans = ans * a % p;
a = a * a % p ,b >>= 1;
}return ans;
}
namespace DSU{
int fa[MX];
void init(){for(int i = 1 ; i < MX ; ++i) fa[i] = i;}
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
void link(int x ,int y){fa[find(x)] = find(y);}
}
using DSU::init;
using DSU::find;
using DSU::link;
int head[MX] ,tot = 1;
struct edge{
int node ,next;
}h[MX << 1];
void addedge(int u ,int v ,int flg = 1){
h[++tot] = (edge){v ,head[u]} ,head[u] = tot;
if(flg) addedge(v ,u ,false);
}
int n ,m;
int acnt;
int au[MX] ,av[MX];
int hson[MX] ,size[MX] ,fa[MX] ,dep[MX];
void dfs(int x ,int f ,int depth){
size[x] = 1 ,fa[x] = f ,dep[x] = depth;
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
dfs(d ,x ,depth + 1) ,size[x] += size[d];
if(size[d] > size[hson[x]]) hson[x] = d;
}
}
int top[MX] ,id[MX] ,cnt ,bot[MX] ,antid[MX];
void dfs2(int x ,int topf){
bot[x] = x ,top[x] = topf ,id[x] = ++cnt ,antid[cnt] = x;
if(hson[x]) dfs2(hson[x] ,topf) ,bot[x] = bot[hson[x]];
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == hson[x] || d == fa[x]) continue;
dfs2(d ,d);
}
}
struct Matrix{
LL A[2][2];
Matrix(){memset(A ,0 ,sizeof A);}
Matrix operator *(const Matrix& B)const{
Matrix C;
for(int i = 0 ; i < 2 ; ++i)
for(int j = 0 ; j < 2 ; ++j)
for(int k = 0 ; k < 2 ; ++k)
C.A[i][j] = (C.A[i][j] + A[i][k] * B.A[k][j]) % MOD;
return C;
}
LL ansA()const{return (A[0][1] + A[1][1]) % MOD;}
LL ansB()const{return A[0][1];}
}T[MX];
struct node{
int l ,r;
Matrix A;
node *lch ,*rch;
}*root;
void pushup(node *x){x->A = x->lch->A * x->rch->A;}
void updm(Matrix &A ,LL a ,LL b){
A.A[0][0] = A.A[0][1] = a;
A.A[1][0] = b ,A.A[1][1] = 0LL;
}
node *build(int l ,int r){
node *x = new node; x->l = l ,x->r = r;
if(l == r){
x->A = T[antid[l]];
x->lch = x->rch = nullptr;
}
else{
int mid = (l + r) >> 1;
x->lch = build(l ,mid);
x->rch = build(mid + 1 ,r);
pushup(x);
}
return x;
}
Matrix query(node *x ,int l ,int r){
if(l <= x->l && x->r <= r) return x->A;
if(l <= x->lch->r && x->lch->r < r)
return query(x->lch ,l ,r) * query(x->rch ,l ,r);
if(l <= x->lch->r) return query(x->lch ,l ,r);
return query(x->rch ,l ,r);
}
void change(node *x ,int p ,LL a ,LL b){
if(x->l == x->r) return updm(x->A ,a ,b);
if(p <= x->lch->r) change(x->lch ,p ,a ,b);
else change(x->rch ,p ,a ,b);
return pushup(x);
}
int divA[MX] ,divB[MX] ,mark[MX];
LL A[MX] ,B[MX];
namespace NORMAL_DP{
LL dp[MX][2];
void dapai(int x ,int f){
A[x] = B[x] = 1LL;
dp[x][0] = dp[x][1] = 1;
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
dapai(d ,x);
dp[x][0] = dp[x][0] * (dp[d][0] + dp[d][1]) % MOD;
dp[x][1] = dp[x][1] * dp[d][0] % MOD;
if(hson[x] != d){
divA[x] += (dp[d][0] + dp[d][1]) % MOD == 0;
divB[x] += dp[d][0] == 0;
if((dp[d][0] + dp[d][1]) % MOD) A[x] = A[x] * (dp[d][0] + dp[d][1]) % MOD;
if(dp[d][0]) B[x] = B[x] * dp[d][0] % MOD;
}
}
debug("dp[%d] = {%lld ,%lld}
" ,x ,dp[x][0] ,dp[x][1]);
}
}
void changeMatrix(int x){
LL a ,b;
a = divA[x] ? 0 : A[x];
b = divB[x] ? 0 : B[x];
if(mark[x]) a = 0;
change(root ,id[x] ,a ,b);
}
Matrix S;
void add(int x){
#define tf fa[top[x]]
Matrix old ,cur;
++mark[x];
while(x){
old = query(root ,id[top[x]] ,id[bot[x]]) * S;
changeMatrix(x);
cur = query(root ,id[top[x]] ,id[bot[x]]) * S;
if(old.ansA() == 0) --divA[tf];
else A[tf] = A[tf] * qpow(old.ansA() ,MOD - 2) % MOD;
if(cur.ansA() == 0) ++divA[tf];
else A[tf] = A[tf] * cur.ansA() % MOD;
if(old.ansB() == 0) --divB[tf];
else B[tf] = B[tf] * qpow(old.ansB() ,MOD - 2) % MOD;
if(cur.ansB() == 0) ++divB[tf];
else B[tf] = B[tf] * cur.ansB() % MOD;
x = tf;
}
}
void del(int x){
Matrix old ,cur;
--mark[x];
while(x){
old = query(root ,id[top[x]] ,id[bot[x]]) * S;
changeMatrix(x);
cur = query(root ,id[top[x]] ,id[bot[x]]) * S;
if(old.ansA() == 0) --divA[tf];
else A[tf] = A[tf] * qpow(old.ansA() ,MOD - 2) % MOD;
if(cur.ansA() == 0) ++divA[tf];
else A[tf] = A[tf] * cur.ansA() % MOD;
if(old.ansB() == 0) --divB[tf];
else B[tf] = B[tf] * qpow(old.ansB() ,MOD - 2) % MOD;
if(cur.ansB() == 0) ++divB[tf];
else B[tf] = B[tf] * cur.ansB() % MOD;
x = tf;
}
}
#undef tf
LL query(){
Matrix ans = query(root ,id[1] ,id[bot[1]]) * S;
return (ans.A[0][1] + ans.A[1][1]) % MOD;
}
int main(){
S.A[0][1] = 1;
init();
n = read() ,m = read();
for(int i = 1 ,u ,v ; i <= m ; ++i){
u = read() ,v = read();
if(find(u) == find(v)){
au[acnt] = u ,av[acnt] = v;
++acnt;
}
else{
debug("%d %d tree
" ,u ,v);
addedge(u ,v);
link(u ,v);
}
}
dfs(1 ,0 ,1);
dfs2(1 ,1);
NORMAL_DP::dapai(1 ,0);
for(int i = 1 ; i <= n ; ++i){
updm(T[i] ,divA[i] ? 0LL : A[i] ,divB[i] ? 0LL : B[i]);
}
root = build(1 ,n);
LL ans = query();
for(int i = 1 ; i < (1 << acnt) ; ++i){
int which = lg2(gray(i) ^ gray(i - 1));
int bc = i & 1;
if(gray(i) & (1 << which)) add(au[which]) ,add(av[which]);
else del(au[which]) ,del(av[which]);
if(bc & 1) ans = (ans - query() + MOD) % MOD;
else ans = (ans + query()) % MOD;
}
printf("%lld
" ,ans);
return 0;
}