P11613 题解

首先转成最大独立集，对图

\bmod p

计数有经典做法，取出前两个点，如果这两个点邻域不同则交换之，得到一个相等的图。

因此这两个点邻域相同，讨论两点间是否有边，如果有边那么两个点至多选一个，看成删除一个点，否则必定同时选或不选，生成一个大小为

2

的点。

那么不断合并大小相同的两个点，最终图上会剩若干大小不同的点，设为

2^{a_1}\sim 2^{a_k}

。

很显然我们的策略就是按

a

从大到小贪心，每个点如果邻域没选就选上。

那么记

m=\sum 2^{a_i}

，先考虑

n

个点得到

m

个这样的组的方案数

f(n,m)

。

记

\mathrm{lowbit}(m)=2^k

，考虑加入最后一个点时

m

的变化过程，首先必定存在

2^0\sim 2^{k-1}

并且不断选择合成才能不生成

<2^k

的点，而生成出

2^k

后，如果原来不存在

2^k

，那么合成过程停止；否则如果把两个

2^k

合成就不存在大小为

2^k

的点了，所以原本有

2^k

的情况下会删除一个

2^k

的点。

那么

f(n,m)=f(n-1,m-1),f(n-1,m+2^k-1)

。

然后考虑

m

向某个

w\subseteq m

转移的方案数，考虑方案数，如果有一个

2^{a_i}\not\in w

，则

a_j<a_i

的点可以任意选择是否与

i

连边。

所以

w\not\in\{m,m-2^k\}

时必定有偶数种连边方案，所以

f(n,m)

只能向

(n,m),(n,m-2^k)

转移答案。

时间复杂度

\mathcal O(n^2)

。

代码：

CPP

#include<bits/stdc++.h> 
using namespace std;
const int MAXN=1<<14|5;
bitset <MAXN> f,g,h,z;
vector <array<int,2>> qy[MAXN];
int n,q;
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>q;
	for(int i=1,x,y;i<=q;++i) cin>>x>>y,n=max(n,x),qy[x].push_back({x-y,i});
	f[0]=1;
	for(int i=1;i<=n;++i) {
		h.reset(),g.reset();
		for(int x=1;x<=i;++x) {
			h[x]=f[x-1]^f[x+(x&-x)-1];
			if(h[x]) g.flip(x),g.flip(x&(x-1));
		}
		f=h;
		for(auto o:qy[i]) z[o[1]]=g[o[0]];
	}
	for(int i=1;i<=q;++i) cout<<z[i]<<"\n";
	return 0;
}

文章操作

相关推荐

评论

P11613 题解