P11613 题解

· · 题解

Problem Link

首先转成最大独立集，对图 \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)。

代码：

#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;
}