专栏文章

图计数 学习笔记

iini2015_____
算法·理论参与者 12已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
1 份
快照标识符
@mkmuelm1
此快照首次捕获于
2026/01/21 01:03
4 周前
此快照最后确认于
2026/02/19 01:17
13 小时前
查看原文
突然发现自己不会图计数，这也太倒闭了。
这里简单讲一些 n≤15,m≤n(n−1)2n\le 15,m\le \frac {n(n-1)}2 的图计数的题目，不会涉及哈集幂科技。

无向图计数

例题 1

P10982 修改版
给你一个 nn 个点 mm 条边的无向图，求边集 E′⊆EE'\subseteq E 的个数，满足 (V,E′)(V,E') 是连通图。
n≤17,m≤n(n−1)2n\le 17,m\le \frac {n(n-1)}{2}
solution
连通性感觉是难以处理的，我们考虑单步容斥，求出来不连通的方案数。
记 fSf_S 为 SS 导出子图连通的方案数，gSg_S 为 SS 导出子图不连通的方案数。
我们记 E(S,T)E(S,T) 为 S→TS\to T 的边数，那么显然有
fS=2E(S,S)−gSf_S=2^{E(S,S)}-g_S
统计 gSg_S，我们不妨任意选一个点 u∈Su\in S，然后钦定集合 TT 是 uu 所在的联通块，于是有 gS=∑{u}⊆T⊂SfT2E(S/T,S/T)g_S=\sum_{\{u\}\subseteq T\subset S}f_T2^{E(S/T,S/T)} 然后 O(3n)O(3^n) 随便做了。

例题 2

ARC105F
给你一个 nn 个点 mm 条边的无向图，求边集 E′⊆EE'\subseteq E 的个数，满足 (V,E′)(V,E') 是连通二分图。
n≤17,m≤n(n−1)2n\le 17,m\le \frac {n(n-1)}{2}
solution
直接计数很困难，我们考虑保证图是一个二分图，然后容斥计算出连通的情况数。
记 SS 导出子图是一个连通二分图的方案数为 fSf_S，是一个二分图的方案数是 gSg_S。
那么和上面一样，显然有
fS=gS−∑{u}⊆T⊂SfTgS/Tf_S=g_S-\sum_{\{u\}\subseteq T\subset S}f_Tg_{S/T}
计算 gSg_S，我们考虑对于一个染色方案求出所有合法方案，直接枚举左部和右部 T,S/TT,S/T，那么贡献就是 2E(T,S/T)2^{E(T,S/T)}。
这个时候，对于每个 kk 个连通块的二分图 GG，其在 gSg_S 中会被计算 2k2^k 次，那么我们最后求出来的答案需要除以 22。
codeCPP
const int N=19,M=(1<<18)+5,mod=998244353,iv2=(mod+1)>>1;
int n,m,T;
int f[M],g[M];
int to[N],pw[M];
#define popc(x) __builtin_popcount(x)
#define lowbit(x) (x&(-x))
inline void upd(int& x){if(x>=mod)x-=mod;}
inline int E(int S,int T){
    int res=0;
    for(int i=0;i<n;i++)if(S>>i&1)res+=popc(to[i]&T);
    return res;
}
int main(){
    n=read(),m=read();
    pw[0]=1; for(int i=1;i<M;i++)upd(pw[i]=pw[i-1]*2);
    while(m--){
        int a=read()-1,b=read()-1;
        to[a]|=1<<b,to[b]|=1<<a;
    }
    for(int s=0;s<(1<<n);s++)for(int t=s;~t;t=t?((t-1)&s):(-1))upd(g[s]+=pw[E(t,s^t)]);
    for(int s=0;s<(1<<n);s++){
        f[s]=g[s]; int u=lowbit(s);
        for(int t=(s-1)&s;t;t=(t-1)&s)if((t|u)==t)
            upd(f[s]+=mod-1ll*f[t]*g[s^t]%mod);
    }
    printf("%lld\n",1ll*f[(1<<n)-1]*iv2%mod);
    return 0;
}
//  Think twice,code once

有向图计数

例题 3

P6846
给你一个 nn 个点 mm 条边的无向图，求把所有边定向的方案数，使得定向后是一个 DAG。
n≤17,m≤n(n−1)2n\le 17,m\le \frac {n(n-1)}{2}
solution
考虑记 fSf_S 为对 SS 这个点集的导出子图 GSG_S 定向的方案数，假如我 T(GS)T(G_S) 是 SS 的导出子图中度数为 11 的点的集合，显然 T(GS)T(G_S) 是一个独立集，那么我们有 fS=fS/T(GS)f_S=f_{S/T(G_S)}。
枚举 TT，直接算会算重，考虑容斥，经典结论是容斥系数是 (−1)∣T∣−1(-1)^{|T|-1}，这个证明其实非常简单啊。
证明
假设 ∣T(GS)∣=k|T(G_S)|=k，我们计算 GG 被计算到的次数。
这个其实是
∑Ø⊂T′⊆T(GS)(−1)∣T′∣−1\sum_{\text{\O} \subset T'\subseteq T(G_S)}(-1)^{|T'|-1}
经典二项式定理，答案为 11。
也就是每个图都只会被算一次，不会算重。
那么有 fS=∑T⊆S(−1)∣T∣−1[T是独立集]fS/Tf_S=\sum_{T\subseteq S} (-1)^{|T|-1}[T \text{是独立集}]f_{S/T}
那么我们提前预处理哪些集合是独立集，然后就随便 DP 了。
时间复杂度 O(3n)O(3^n)。
然后原题要多乘一个 m2\frac m 2。
codeCPP
const int N=19,M=(1<<18)+5,mod=998244353,iv2=(mod+1)/2;
int n,m,T;
bool h[M]; int f[M];
#define popc(x) __builtin_popcount(x)
inline void upd(int& x){if(x>=mod)x-=mod;}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read()-1,v=read()-1;
        h[(1<<u)|(1<<v)]=1;
    }
    for(int i=0;i<n;i++)for(int j=0;j<(1<<n);j++)if(j>>i&1)h[j]|=h[j^(1<<i)];
    f[0]=1;
    for(int S=0;S<(1<<n);S++){
        for(int T=S;T;T=(T-1)&S)if(!h[T]){
            if(popc(T)&1)
                upd(f[S]+=f[S^T]);
            else
                upd(f[S]+=mod-f[S^T]);
        }
    }
    printf("%lld\n",1ll*f[(1<<n)-1]*m%mod*iv2%mod);
    return 0;
}
//  Think twice,code once

例题 4

主旋律
给你一个 nn 个点 mm 条边的有向图，求边集 E′⊆EE'\subseteq E 的个数，满足 (V,E′)(V,E') 是强连通图。
n≤15,m≤n(n−1)n\le 15,m\le n(n-1)
solution
考虑把图进行缩点，那么合法当且仅当缩完之后是一个单点。
我们记 fSf_S 为 SS 的导出子图强连通的方案数，gSg_S 为 SS 的导出子图不强连通的方案数，依旧 fS=2E(S,S)−gSf_S=2^{E(S,S)}-g_S 考虑不强连通等价于缩点之后存在多个点，我们拆掉那些不是全集，且入度为 00 的点。
我们记 GG 缩点后的图为 G′G'，那么我们需要枚举 G′G' 中入度为 00 的点集 T′T'，有容斥系数 (−1)∣T′∣−1(-1)^{|T'|-1}。
我们对于一个 TT，∣T′∣|T'| 是不定的，于是我们把 (−1)∣T′∣−1(-1)^{|T'|-1} 放到状态里面，我们记 hSh_S 是把 SS 缩成 kk 个单点，系数为 (−1)k−1(-1)^{k-1} 时，所有方案的系数之和。
那么有
gS=∑Ø⊂T⊂ShT2E(S,S/T)hS=fS−∑{u}⊆T⊂SfThS/Tg_S=\sum_{\text{\O} \subset T\subset S}h_T2^{E(S,S/T)}\\ h_S=f_S-\sum_{\{u\}\subseteq T\subset S}f_Th_{S/T}
然后 O(3n)O(3^n) 随便做。
codeCPP
const int mod=1e9+7;
const int N=15,M=1<<N,inf=1e9+7;
int n,m;
int f[M],g[M],h[M];
int to[N];
int pw[M];
#define popc(x) __builtin_popcount(x) 
#define lowbit(x) (x&(-x))
inline void upd(int& x){if(x>=mod)x-=mod;}
int E(int S,int T){
	int res=0;
	for(int i=0;i<n;i++)if(S>>i&1)res+=popc(to[i]&T);
	return res;
}
int main(){
	n=read(),m=read();
	pw[0]=1; for(int i=1;i<M;i++)pw[i]=pw[i-1]*2%mod; 
	while(m--){
		int u=read()-1,v=read()-1;
		to[u]|=(1<<v);
	}
	for(int s=1;s<(1<<n);s++){
        int u=lowbit(s);
        for(int t=(s-1)&s;t;t=(t-1)&s)if(t&u)
            upd(h[s]+=mod-1ll*f[t]*h[s^t]%mod);
		for(int t=s;t;t=(t-1)&s)
            upd(g[s]+=1ll*h[t]*pw[E(s,s^t)]%mod);
        upd(f[s]=pw[E(s,s)]-g[s]+mod),upd(h[s]+=f[s]); 
	}
	printf("%d\n",f[(1<<n)-1]);
	return 0;
}

习题

习题 1

ABC306H
给你 mm 个二元组 (x,y)(x,y)，以及 nn 个变量 aia_i，你要给每一个二元组选择 ax<aya_x<a_y 或 ax=aya_x=a_y 或 ax>aya_x>a_y，使得存在一组解，求合法方案数。
n≤17,m≤n(n−1)2n\le 17,m\le \frac {n(n-1)}{2}
solution
典完了，相信大家在学会主旋律的基础上都随便秒掉这个题。
考虑题意就是无向边缩点之后是一个 DAG，我们依旧钦定独立集，记 fSf_S 为 SS 的导出子图的定向方案，hSh_S 为 SS 被缩成独立集后的 (−1)size−1(-1)^{size-1}。
那么依旧 fS=∑T⊆ShTfS/Tf_S=\sum_{T\subseteq S} h_Tf_{S/T} 预处理 hh，然后 O(3n)O(3^n) 随便做。
codeCPP
const int N=17,M=1<<17,mod=998244353;
int n,m,T;
int to[N];
int h[M],f[M];
inline void upd(int& x){if(x>=mod)x-=mod;}
int fa[N];
int find(int x){
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y){
	x=find(x),y=find(y);
	fa[x]=y;
}
int main(){
	n=read(),m=read();
	while(m--){
		int a=read()-1,b=read()-1;
		to[a]|=1<<b,to[b]|=1<<a;
	}
	for(int s=1;s<(1<<n);s++){
		for(int i=0;i<n;i++)fa[i]=i;
		for(int i=0;i<n;i++)if(s>>i&1)
			for(int j=0;j<n;j++)if(to[i]>>j&1)if(s>>j&1)
				merge(i,j);
		h[s]=mod-1;
		for(int i=0;i<n;i++)if(s>>i&1)if(fa[i]==i)h[s]=mod-h[s];
	}
	f[0]=1;
	for(int s=1;s<(1<<n);s++)
		for(int t=s;t;t=(t-1)&s)
			upd(f[s]+=1ll*h[t]*f[s^t]%mod);
	printf("%d\n",f[(1<<n)-1]);
}

习题 2

重塑时光
给你一个 nn 个点 mm 条边的有向图 GG，你有一个随机排列 pp，你会在 pp 上随机切 kk 刀，求能够将 k+1k+1 个连续段重排列成 p′p' 后，使得 p′p' 是 GG 的一个拓扑序。
n≤15,m≤n(n−1)2n\le 15,m\le \frac {n(n-1)}2
solution
不难发现一个切割方案能插板法对应到序列上放了 kk 个隔板，于是总的方案数就是 (n+kk)n!\binom{n+k}kn!。
不妨认为我们在给 nn 个点染成 k+1k+1 种颜色，那么对于一个染色方案，其合法当且仅当把所有同颜色的点缩成一个点之后，图是一个 DAG。
对于一个合法的染色方案，我们还可以给每个集合选择一个拓扑序，那么会有一个所有导出子图拓扑序个数之积的系数，我们要求的就是所有合法方案的系数之和。
首先可以预处理一个 hSh_S 表示 GSG_S 的拓扑序个数，可以随便 O(2nn)O(2^nn) DP 处理。
我们记 fS,kf_{S,k} 为把点集 SS 染成 kk 种颜色的方案数，gS,kg_{S,k} 为把点集 SS 染成 kk 种颜色且每个颜色是独立集的方案数，带有 (−1)k−1(-1)^{k-1} 的系数。那么显然有
fS,k=∑Ø⊂T⊆S,a+b=kgT,afS/T,b[E(S/T,T)=0]gS,k=−∑{u}⊆T⊂ShTgS/T,k−1[E(T,S/T)=E(S/T,T)=0]f_{S,k}=\sum_{\text{\O}\subset T\subseteq S,a+b=k}g_{T,a}f_{S/T,b}[E(S/T,T)=0]\\ g_{S,k}=-\sum_{\{u\}\subseteq T\subset S}h_Tg_{S/T,k-1}[E(T,S/T)=E(S/T,T)=0]
直接 DP 可以做到 O(3nn2)O(3^nn^2)。
然后你发现瓶颈在于 ff 的处理，发现 ff 的转移是一个多项式卷积的形式，那么我们直接拉插处理即可，需要做 nn 遍原来的问题，时间复杂度 O(3nn)O(3^nn)。
codeCPP
const int N=17,M=1<<15,mod=1e9+7;
int to[N];
int h[M],g[M][N];
int fv[M],gv[M],a[N],b[N],fx[N];
int st[M];
int fac[N<<1],ifac[N<<1];
int n,m,k;
inline void upd(int& x){if(x>=mod)x-=mod;}
inline int fpow(int a,int b){
	int res=1;
	for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)res=1ll*a*res%mod;
	return res;
}
inline void initfac(){
	fac[0]=1; for(int i=1;i<(N<<1);i++)fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=0;i<(N<<1);i++)ifac[i]=fpow(fac[i],mod-2);
}
inline bool E(int S,int T){return (st[S]&T);}
void Langrange(){
	for(int i=0;i<=n+1;i++){
		int v=1;
		for(int j=0;j<=n+1;j++)if(j!=i)
			v=1ll*v*(i-j+mod)%mod;
		v=1ll*fpow(v,mod-2)*fx[i]%mod;
		memset(b,0,sizeof b); b[0]=1;
		for(int j=0;j<=n+1;j++)if(j!=i){
			for(int w=n;~w;w--)
				upd(b[w+1]+=b[w]),
				b[w]=1ll*b[w]*(mod-j)%mod;
		}
		for(int j=0;j<=n+1;j++)
			upd(a[j]+=1ll*v*b[j]%mod);
	}
}
int main(){
	n=read(),m=read(),k=read();
	initfac();
	while(m--){
		int a=read()-1,b=read()-1;
		to[a]|=1<<b;
	}
	for(int s=0;s<(1<<n);s++)
		for(int i=0;i<n;i++)if(s>>i&1)
			st[s]|=to[i];
	h[0]=1;
	for(int s=1;s<(1<<n);s++)
		for(int i=0;i<n;i++)if(s>>i&1)
			if(!(to[i]&s))upd(h[s]+=h[s^(1<<i)]);
	g[0][0]=mod-1;
	for(int s=0;s<(1<<n);s++){
		int u=__lg(s&(-s));
		for(int t=s;t;t=(t-1)&s)if(t>>u&1)if(!E(t,s^t) && !E(s^t,t))
			for(int i=1;i<=n+1;i++)
				upd(g[s][i]+=mod-1ll*h[t]*g[s^t][i-1]%mod);
	}
	for(int x=0;x<=n+1;x++){
		for(int s=0;s<(1<<n);s++){
			gv[s]=0;
			for(int i=n+1;~i;i--)
				gv[s]=(1ll*gv[s]*x+g[s][i])%mod;
		}
		fv[0]=1;
		for(int s=1;s<(1<<n);s++){
			fv[s]=0;
			for(int t=s;t;t=(t-1)&s)if(!E(s^t,t))
				upd(fv[s]+=1ll*fv[s^t]*gv[t]%mod);	
		}
		fx[x]=fv[(1<<n)-1];
	}
	Langrange();
	int ans=0;
	for(int i=1;i<=k+1;i++)
		upd(ans+=1ll*a[i]*fac[k+1]%mod*ifac[k+1-i]%mod);
	ans=1ll*ans*ifac[n+k]%mod*fac[k]%mod;
	printf("%d\n",ans);
}

习题 3

岁月
给你一个 nn 个点 mm 条边的边带权无向图 GG，每条边被拆成两条有向边后得到 G′G'，G′G' 的每条边有 12\frac 1 2 的概率消失，问 G′G' 的最小外向生成树的权值与 GG 的最小生成树的权值相等的概率。
n≤15,m≤n(n−1)2n\le15,m\le \frac{n(n-1)}2
solution
首先考虑 C 性质，每条边的边权都相等。那么我们需要求存在一个外向生成树的概率。
不妨枚举可以成为根的集合 RR，记以 RR 集合可能成为根的概率为 ansRans_R。
考虑 RR 成为根的条件：
  1. RR 内部强连通。
  2. R→U/RR\to U/R 的路径存在。
  3. U/R→RU/R \to R 的路径不存在。
第一个条件就是主旋律了。
第三个条件考虑所有 U/R→RU/R\to R 的边必然不存在，需要乘上一个系数 2−E(U/R,R)2^{-E(U/R,R)}。
第二个条件考虑 DP 处理，我们记 fSf_S 为从 RR 出发，考虑 GSG_S 时，可以到达 SS 集合的概率，转移就是容斥，枚举一个不能到达的集合 TT，有
fS=1−∑T∩R=Ø,T⊆SfS/T2−E(S/T,T)f_S=1-\sum_{T\cap R=\text{\O},T\subseteq S}f_{S/T}2^{-E(S/T,T)}
第二个条件满足的概率就是 fUf_U。
不难发现三个条件相互独立，把三个概率乘在一起就是 ansRans_R。
直接做是 O(4n)O(4^n) 的，瓶颈在于第二个条件。
考虑 DP 式子的组合意义，我们相当于初始在集合 RR 的一个超集 R′R'，对于一个集合 TT，我们可以走到 TT 的超集 SS，路径权值为 −2−E(T,S/T)-2^{-E(T,S/T)}，问你走到 UU 的路径权值之和。
我们把这个问题反过来，对于每个集合求出 UU 到其的路径权值之和，显然可以做到 O(2npoly(n))O(2^n\text{poly}(n))，然后我们只需要求一个超集和即可。
这样我们可以把 C 性质做到 O(3n)O(3^n)，可以获得 64 pts，估计场上拿到 64 就很足够了。
我们把这个做法扩展到一般情况。
考虑如何判断 G′G' 是否合法。
分析 Kruskal 的过程，我们按照边权 ww 分层考虑，对于每一层 ww，我们都需要 G′G' 满足其每个弱连通块和 GG 相同，并且每个弱连通块都需要存在外向生成树。不难发现这个条件是充要的。
我们记 ansSans_S 为 SS 在其弱连通块内部成为根的集合的概率，按层维护，最后 ∑ansS\sum ans_S 即为答案。
先仿照上面 O(4n)O(4^n) 的解法，对于当前的弱连通块 UU 每次枚举根集合 RR，计算 ansRans_R，然后依旧分三个 part。
  1. RR 强连通。
  2. R→U/RR \to U/R 的路径存在。
  3. U/R→RU/R \to R 的路径不存在。
这里的条件 3 依旧容易处理。
条件 1 是一个主旋律状物，记 scSsc_S 为点集 SS 所在的弱连通块的集合。我们一次转移一个连通块，我们认为每个连通块内部是强连通的，转移是容易的。
对于条件 2，记 beSbe_S 为 SS 成为 scSsc_S 的根集合的概率，记 fSf_S 为从 RR 出发，考虑 GSG_S 时，可以到达的根的集合为 SS 的概率，转移是
fS=[S∩scR=R](beS−∑T⊂S,scT∩scS/T=Ø2−E(scS/T,T)fS/TbeT)f_S=[S\cap sc_R=R](be_S-\sum_{T\subset S,sc_T\cap sc_{S/T}=\text{\O}}2^{-E(sc_{S/T},T)}f_{S/T}be_T)
然后 ff 对于 ansSans_S 的贡献就是包含了所有连通块的 SS 的 fSf_S 之和。
那么可以做到 O(4n)O(4^n)。
同理可以通过反向 DP 做到 O(3n)O(3^n)。
你发现我们单层是 O(3n)O(3^n) 的，全局是一个等比数列求和，还是 O(3n)O(3^n)，可以通过。
codeCPP
const int N=15,M=1<<N,K=555,mod=1e9+7,iv2=(mod+1)/2;
int n,m,T;
int to[N],cnt[M],bl[N],_bl[N],sc[M],_sc[M],ans[M];
int f[M],g[M],h[M],pw[K],dp[M],be[M];
bool fl[M],vs[M];
#define popc(x) __builtin_popcount(x) 
#define lowbit(x) (x&(-x))
#define mem(x) memset(x,0,sizeof(x))
inline void upd(int& x){if(x>=mod)x-=mod;}
void init(){pw[0]=1; for(int i=1;i<K;i++)pw[i]=1ll*pw[i-1]*iv2%mod;}
int sE(int S,int T){int res=0; for(int i=0;i<n;i++)if(S>>i&1)res+=popc(to[i]&T); return res;}
int E(int S,int T){return (cnt[S|T]-cnt[S]-cnt[T])>>1;}
struct Edge{
	int a,b,c;
	bool operator<(Edge t)const{return c<t.c;}
}e[K];
int fa[N],bel[N];
int find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]);}
void merge(int x,int y){x=find(x),y=find(y); if(x==y)return ; assert(x<n); assert(y<n);bl[y]|=bl[x]; fa[x]=y;}
void Memset(){mem(fa),mem(bel),mem(to),mem(cnt),mem(bl),mem(_bl),mem(sc),mem(_sc),mem(ans),mem(f),mem(g),mem(h),mem(fl),mem(vs),mem(dp),mem(be);}
void solve(){
	Memset();
	n=read(),m=read(); int U=(1<<n)-1;
	for(int i=1;i<=m;i++)e[i].a=read()-1,e[i].b=read()-1,e[i].c=read();
	sort(e+1,e+1+m);
	for(int i=0;i< n;i++)bl[i]=1<<i;
	for(int i=0;i< n;i++)ans[1<<i]=1,fa[i]=i;
	for(int L=1,R=0;L<=m;L=R+1){
		while(R!=m && e[R+1].c==e[L].c)++R;
		for(int i=0;i<n;i++)bel[i]=find(i);
		mem(to),mem(fl),mem(be),mem(dp),mem(f),mem(g),mem(h),mem(dp);
		for(int i=0;i<n;i++)_bl[i]=bl[i];
		for(int s=0;s<=U;s++)
			for(int i=0;i<n;i++)if(s>>i&1)
				_sc[s]|=_bl[bel[i]];
		for(int i=L;i<=R;i++)if(bel[e[i].a]!=bel[e[i].b]){
			merge(e[i].a,e[i].b);
			to[e[i].a]|=1<<e[i].b,to[e[i].b]|=1<<e[i].a;
			fl[bl[find(e[i].b)]]=1;
		}
		for(int s=0;s<=U;s++)
			cnt[s]=sE(s,s);
		for(int s=0;s<=U;s++)if(fl[s])
			for(int t=s;t;t=(t-1)&s)fl[t]=1;
		be[0]=1;
		for(int s=1;s<=U;s++)if(fl[s]){
			int u=__lg(lowbit(s)),su=_bl[bel[u]],st=s&(U^su);
			be[s]=1ll*be[st]*ans[su&s]%mod; sc[s]=0;
			for(int i=0;i<n;i++)if(s>>i&1)sc[s]|=bl[find(i)];
		}
		for(int s=1;s<=U;s++)if(fl[s]){
			int u=lowbit(s);
			for(int t=s;t;t=(t-1)&s)if((t&u)&&(_sc[s^t]&_sc[t])==0)
				upd(h[s]+=mod-1ll*f[t]*h[s^t]%mod*pw[E(_sc[s^t],t)+E(s^t,_sc[t])]%mod);
			for(int t=s;t;t=(t-1)&s)if((_sc[s^t]&_sc[t])==0)
				upd(g[s]+=1ll*h[t]*pw[E(_sc[s^t],t)]%mod);
			upd(f[s]=1-g[s]+mod); upd(h[s]+=f[s]);
		}
		for(int s=0;s<=U;s++)if(fl[s])
			if(_sc[s]==sc[s])dp[s]=1;
		for(int s=U;s;s--)if(fl[s])
			for(int t=(s-1)&s;t;t=(t-1)&s)
				if((_sc[t]&_sc[s^t])==0)
					upd(dp[s^t]+=mod-1ll*dp[s]*pw[E(_sc[s^t],t)]%mod*be[t]%mod);
		for(int s=U;s;s--)if(fl[s])
			dp[s]=1ll*dp[s]*be[s]%mod;
		for(int s=U;s;s--)if(fl[s]){
			ans[s]=0; int qs=s^sc[s];
			for(int t=qs;~t;t=t?((t-1)&qs):-1)
				if((_sc[s]&_sc[qs^t])==0)
					upd(ans[s]+=dp[sc[s]^t]);
			ans[s]=1ll*ans[s]*pw[E(sc[s]^_sc[s],s)]%mod*f[s]%mod%mod;
		}
	}
	int res=0; for(int i=0;i<=U;i++)upd(res+=ans[i]);
	printf("%d\n",res);
}
signed main(){
	init();
	int Testid=read(); T=read();
	while(T--)solve();
}

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...