题意：给出一个数 ，求最大元素
的线性空间数量，对 取模。
计数线性空间，我们有必要了解一个叫“简化线性基”的东西。
下文的矩阵中，每一行就是线性基每一个元素的二进制拆分，从左到右是从高位到低位。
一般我们构建的线性基，在每一行的第一个 上方，还可能有其它的 ，比如这样：
在上面的例子中，我们把第一行异或上第二行，就可以得到一个本质相同的线性基：
熟悉线性代数的读者可能知道，这就是一个简化阶梯形矩阵。
这样的矩阵满足对于每行的第一个非 元素，它的上方全都是 。
这样的线性基被成为简化线性基，它具有一些其它线性基没有的性质：
- 这种基能张成的最大元素就是每一行的异或和（最高位选了肯定更优）
- 一个简化线性基唯一对应一个线性空间，因为两个简化线性基不能通过行与行的相互异或来得到对方
这两条性质恰恰与题目的限制吻合。
我们只需计数每行的异或和
，且每行第一个 上方都是 的矩阵个数即可。
数位 DP，设状态 表示现在处理到第 列，线性基一共加入了
个元素，当前的异或和有没有顶到上界。
分类讨论：
- 如果没有顶到上界，那么对于这一列，我们可以不新开元素，已经加入的
个元素在这一列就可以随意取值，方案数为
，如果新开元素，已有的元素在这一列必须为 ，方案数为 。
- 如果顶到了上界：
- 如果我们令这一位的异或和为 ，那么就无法新开元素，只能让已有的 个元素保证异或和为 ，方案数为 。
- 如果我们令这一维的异或和为 ，我们可以新开一个元素，也可以不新开元素，并保证已有的元素异或和为
，方案数也为 （注意特判 的情况）
本题至此已经结束，是一道考察对线性基理解和相关应用的好题，如果有线性代数的知识储备，理解线性基也不是什么难事。
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 40,P = 1e9 + 7;
int f[N][N][2];
int Pow2[N];
int K;
int dfs(int pos,int cnt,int done)
{
if(pos == -1) return 1;
if(~f[pos][cnt][done]) return f[pos][cnt][done];
int res = 0,num = ((long long)K >> pos) & 1;
if(!done)
res = (dfs(pos - 1,cnt + 1,done) + 1ll * Pow2[cnt] * dfs(pos - 1,cnt,done) % P) % P;
else
{
res = 1ll * (cnt ? Pow2[cnt - 1] : 1) * dfs(pos - 1,cnt,!num) % P;
if(num)
res = (res + 1ll * (cnt ? Pow2[cnt - 1] : 0) * dfs(pos - 1,cnt,1) % P) % P,
res = (res + dfs(pos - 1,cnt + 1,1)) % P;
}
f[pos][cnt][done] = res;
return res;
}
int main()
{
cin >> K;
Pow2[0] = 1;
for(int i = 1;i < N;i++)
Pow2[i] = 2ll * Pow2[i - 1] % P;
memset(f,-1,sizeof f);
cout << dfs(N - 1,0,1) << endl;
return 0;
}
|