题意

定义一个集合 $S$ 是好的,当且仅当:
1. $\forall x\in S,y \in S $ 有 $x \oplus y \in S$,这里 $\oplus$ 是异或操作。
2. 集合最大值 $\leq n$

求这样的集合的个数,模 $10 ^9+7$

题解

这是个好题(至少我觉得我是想不出来)
首先一个观察是这样的集合一定是由一组线性基生成出来的,我们只需要搞出一个让线性基和集合的一一对应关系,就可以很方便的 dp 了。
我们考虑用线性基求最大异或和的时候,我们需要使用高斯消元每次选取出第一位非 $0$ 位最靠前的那一个向量,去消掉这一位上其他的 $1$,如果有的变成 $0$ 了说明能被线性组合出来不合法。观察消元后的线性基,我们可以发现存在一些列只有一个 $1$(主元列),我们对这个结果进行计数。
数位 $dp$ :设 $f_{i,j,lim}$ 表示从高往低考虑到第 $i$ 位,已经用了 $j$ 个向量去限定,现在是否卡上界。分类讨论:
1. 不卡上界
考虑这一位可以使用一个单独的向量限定为 $1$,也可以在已经有的向量里限定。
如果开一个单独的向量那么必须钦定目前已有的向量这一位都是 0,就是 $f_{i-1,j+1,0}$ 种方案。
如果这一位用之前的向量限定,那么每个向量这一位都可以填 $0$ 和 $1$,就有 $f_{i-1,j,0}*2^j$ 种方案。
2. 卡上界
这里和上面唯一不同的地方就是我们需要求出限定这一位为 $0/1$ 的方案。由于最大值是所有向量异或起来,那么如果这一位有奇数个 $1$ 那么这一位就是 $1$,否则就是 $0$,方案数都是 $2^{j-1}$。但是如果之前还没有基这一位就只能是 $0$ 需要特判一下(

代码

挺好写的

/*
 * Author: RainAir
 * Time: 2019-10-08 10:02:13
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 40+5;
const int ha = 1e9 + 7;
int f[MAXN][MAXN][2],pw[MAXN];
// 第 i 位搞了 j 个基
int a[MAXN],len;

inline int dfs(int i,int j,int lim){
    if(!i) return 1;
    if(f[i][j][lim] != -1) return f[i][j][lim];
    int ans = 0;
    if(!lim){
        (ans += 1ll*dfs(i-1,j,0)*pw[j]%ha) %= ha;
        (ans += dfs(i-1,j+1,0)) %= ha;
    }
    else{
        (ans += (1ll*dfs(i-1,j,!a[i])*(!j ? 1 : pw[j-1])%ha))%=ha;
        if(a[i]){
            (ans += dfs(i-1,j+1,1)) %= ha;
            (ans += (1ll*dfs(i-1,j,1)*(!j ? 0 : pw[j-1])%ha)) %= ha;
            // 前面没有基,这一位只能是 0
        }
    }
    return f[i][j][lim] = ans;
}

int main(){
    CLR(f,-1);
    pw[0] = 1;
    FOR(i,1,MAXN-1) pw[i] = (pw[i-1]<<1)%ha;
    int x;scanf("%d",&x);
    while(x) a[++len] = x&1,x >>= 1;
    printf("%d\n",dfs(len,0,1));
    return 0;
}

版权属于:RainAir

本文链接:https://blog.aor.sd.cn/archives/843/

转载时须注明出处及本声明

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏