题意:

给你一个数n,你要从1\to n个数字中选出一个集合,满足

\forall a,b\in S
(a\ xor\ b)\in S

那么我们称这个集合是好的,输出方案数对于1e9+7取膜…..

分析:

首先线性基是什么:

线性基可以理解为集合 S 在异或运算中的压缩,即集合 S 的线性基中的元素进行异或运算可以表示出 S 集合中的元素进行异或运算的所有结果。

我们来看一些概念:

张成 (span) :

S 的所有子集(包括空集)的异或和组成的集合,叫做集合 S 的张成 (span)

线性相关:

如果集合 S 中的一个元素,去除 s_j 之后的集合 S′ 的张成 span(S’) 中,仍然包括 s_j, 则称集合 S 是线性相关的。
我们可以通俗一点讲,即 s_j 是可以通过S 中除了 s_j 的其他元素 异或得到,就称集合 S 是线性相关的。
否则,若不存在这样的元素 s_j ,则称集合 S 是线性无关的。
若集合 S 是线性相关的,那么去除这个元素之后,集合的span 不会发生改变。

线性基:一个集合 B能成为集合 S 的线性基,当且仅当
1. 集合 B 是线性无关的。
2. 集合 S\subseteq span(B)

我们可以根据上面发现:
1. 集合 B 的任何一个真子集都不可能是线性基。
2. 集合 S 中的每一个元素都可以被 B 中的一些元素异或得到。

然后我们来证明一下一个S集合有多个线性基….
比如S_1包含二进制下的数字11,01,那么span(S_1)包含了11,10,01,00
又有S_2包含二进制下的数字10,01,那么span(S_2)包含了11,10,01,00
易得一个集合可以有多个线性基….

然后我们思考怎么构建一个集合的线性基:
假设我们原先集合里有很多元素a_1,a_2,a_3,a_4,…..
然后我们构建一个数组num[100],num[i]表示线性基中二进制下最大位是i的元素,由于线性基是线性无关的,所以,对于一个线性基num[i]只有一个元素…
我们考虑怎么构建它,比如我们现在准备加入a_i,他的二进制表示位1010100101,如果此时num[10]没有元素,那么我们直接把a_i赋给num[10],如果此时num[10]里面有元素了,那么我们把这个数字异或上当前num[i](已知有x,y,x,y表示的线性基和x,x\ xor \ y是等价的,自己去想),然后我们把a_i变成了a_i \ xor \ num[10],再继续进行上述操作,可是如果a_i在若干次操作以后变成0那么我们直接抛弃他….(因为0没有意义)
这样子经过n次操作,我们就得到了a_?的的线性基….
以上就是线性基的正常构建方法

然后我们来看上面这道题目,我们可以用线性基来表示题目中符合条件的集合,但是由于一个集合可以有多个线性基,所以直接算会重复.所以我们需要找到一种线性基的构造方法使得每一个集合对应的线性基是唯一的….
我们构造一种线性基,如果num[i]有值,那么其他的线性基里的元素的第i位都为0,我们可以知道这样子构造出来的线性基是唯一的,因为如果要让一个数字的第i位为1,那么必须xor上num[i]这个数…….

这个东西我们用数位dp写,dp[i][j][0/1]表示现在枚举到了第i位,上面已经取了j个基,然后1表示前面取的基是不是和n的前几位对应上了,0反之
(取满表示,我现在有一个n=11110(二进制),我的num[5,4,3,2]都取了基)
然后我详细写一下转移:
当前状态是dp[i][j][k]

add(x[i-1][j][0],(1LL<<j)*x[i][j][0]%mod);//如果下一位不取,那么i的位置可以顺便放有2^j种方法
add(x[i-1][j+1][0],x[i][j][0]%mod);//如果下一位取,那么只有一种放法...
if((n>>(i-1))&1)//如果n的下一位是1
{
    add(x[i-1][j][1],(j?(1<<j-1):0)*x[i][j][1]%mod);//那么我们可以考虑前面取满的情况
    add(x[i-1][j][0],(j?(1<<j-1):1)*x[i][j][1]%mod);
    add(x[i-1][j+1][1],x[i][j][1]);
}
else add(x[i-1][j][1],(j?(1<<j-1):1)*x[i][j][1]%mod);

代码自己慢慢看…

全代码:

#include<bits/stdc++.h>
#define LL long long
#define int LL
#define P pair<int,int>
const LL N=3e3+10;
const LL mod=1e9+7;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
LL n,ans;
LL x[34][34][5];
void add(LL &a,LL b){a+=b;while(a>=mod)a-=mod;}
signed main()
{
    read(n);
    x[32][0][1]=1;
    for(int i=32;i>=1;i--)
        for(int j=0;j<=32;j++)
        {
            add(x[i-1][j][0],(1LL<<j)*x[i][j][0]%mod);
            add(x[i-1][j+1][0],x[i][j][0]%mod);
            if((n>>(i-1))&1)
            {
                add(x[i-1][j][1],(j?(1<<j-1):0)*x[i][j][1]%mod);
                add(x[i-1][j][0],(j?(1<<j-1):1)*x[i][j][1]%mod);
                add(x[i-1][j+1][1],x[i][j][1]);
            }
            else add(x[i-1][j][1],(j?(1<<j-1):1)*x[i][j][1]%mod);
        }
    for(int i=0;i<=32;i++)
        add(ans,(x[0][i][0]+x[0][i][1])%mod);
    printf("%lld\n",ans);
    return 0;
}

郎sk神仙在5-8放了这道题目…..

Leave A Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注