看上去就很牛的计数题，哇酷哇酷！
题目链接。
题意
一个图
的点覆盖为一个点集 ，使得对于每一条边 都有 或 。
组询问，每一次询问有多少张
个点的简单无向图，其最小点覆盖大小为 。
答案对 取模。
，。
题解
这道题的模数是 ，这显然非常重要。
考虑一张图，设 为点 的邻域（即邻居构成的集合）。
考虑若 ，那么我们可以交换这两个点向外的连边，构成一张新的图。
这张新的图的最小点覆盖大小显然和原图相等。
由于这是一个一一对应的关系，每一张
的图都能找到一张与自己不同的图对应，并且这个对应的关系是互逆的。
也就是说， 的图数量一定是 的倍数，而这道题模数是 ，所以我们可以不对这种图进行计数。
那么再按照
之间有没有边来分个类：
中间有连边，那么这两个点里面至少需要选 个点。
由于这两个点完全等价，我们不妨直接把点 删掉，现在余下 个点，需要求出最小点覆盖大小为 方案数。
中间没有边，那么最优方案里面一定有两个点同时被选中或者两个点同时不被选中。
我们不妨直接将两个点合并，得到一个权重为 的点。
这两种情况下，我们的点数都减少了 。
并且我们可以发现，只要当前存在两个权重相等的点，我们就可以一直合并。
合并到最后会形成若干个点，其权重均为 的次幂且权重互不相同，非常的牛！
设 表示将 个点的图变成一个总权重为 的图，有多少种合并方案。
考虑初始有一个空图，然后每一次往进加一个权重为 的点，重复 次的过程。
每一次加点的时候，如果原图不存在权值为 的点，过程就结束了。
否则可以选择合并或删除，删除的话，图不变，过程结束；合并的话会把原图权值为
的点删掉，然后加上一个权值为
的点。
设 ，那么点
一定是最后一次加点的时候涉及到的位置：
-
这个点由最后一次加点之后，合并了若干次得到。方案数为 。
- 这个点本身就存在，加完第
个点后，新加的点一路合并上来，在
这一位选择了删除，方案数为 。
也就是说有 。
再设 表示有多少张 个点的图，其最小点覆盖大小为 ，也就是我们要求的答案。
考虑一张缩完以后的图，只需要知道点直接的连边，就能贪出最小点覆盖出来。
设
为点权最小的那个点，考虑如下几种情况：
整张图里面没有边，此时最小点覆盖为 ，由于前面还有 个必须选的点，所以有 ；
整张图只选择了点 ，那么剩下的点直接一条边都不能有。
到剩下的点直接可以随便连边，但是至少需要有一条边。
假设剩下了 个点，那么方案数为
，一定为奇数。
所以这部分的贡献是 。
至少选择了一个
之外的点，设点权最大的被选择的点为 。
由于点
被选择，所以我们改变一下
这条边的状态，最小点覆盖答案不会改变。
也就是说，这部分方案数是偶数，不用计算。
这样我们就把
算出来了，预处理好直接回答询问即可。
时间复杂度 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
using pl=pair<ll,ll>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int L=16384;
bitset<L>f[L];
bitset<L>g[L];
inline int lowbit(int i){ return i&(-i);}
int main()
{
f[0][0]=1;
for(int n=1;n<L;n++) for(int m=1;m<=n;m++)
{
f[n][m]=f[n-1][m-1]^f[n-1][m+lowbit(m)-1];
if((int)f[n][m]) g[n][n-m].flip(),g[n][n-m+lowbit(m)].flip();
}
int T=read();
while(T--)
{
int n=read(),m=read();
printf("%d\n",(int)g[n][m]);
}
return 0;
}
|