正文

【做题】CF388D. Fox and Perfect Sets——线性基&数位dp

IP云
IP云V管理员/4 阅读
12/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

原文链接 https://www.cnblogs.com/cly-none/p/9711279.html

题意：求有多少个非空集合\(S \subset N\)满足，\(\forall a,b \in S, a \bigotimes b \in S\),且\(S\)中的最大元素不超过\(n\)。对\(10^9 + 7\)取模。

\(n \leq 10^9\)

显然，每个合法的集合\(S\)都可以由一个线性基来生成。然而，一个集合可以有多个线性基。如果我们能让每个合法集合和每个符合某条件的线性基一一对应，那么我们就能把问题转化为对某类线性基的计数。

考虑对线性基进行高斯消元。结果就是，在线性基中的每一位，要么是一个基的最高位，那么其他的基上的这一位都是0；否则所有基上这一位可以任意填。因为它们可以由任何线性基高斯消元得到，所以每一个合法集合都能有这样的一个线性基。同样，每一个线性基可以生成一个合法的集合。剩下的问题就在于，证明所有不同的高斯消元后的线性基，生成的集合是不同的。

  • 两个线性基的基数不同或基的最高位不同。那么它们生成的集合显然不同。
  • 基数和每个基的最高位都相同。考虑两个线性基中最大的不相同的基。我们取出其中的一个基，尝试在另一个线性基中表达这个数。但当我们遇到它们不相同的最高一位时，因为这一位可以是1或0，所以没有一个基的最高一位是这一位，所以那个基不能被另一个线性基表达。那么，这两个线性基生成的集合就是不同的。

接下来，我们对线性基做dp就可以了。容易得到，高斯消元后的线性基，能表达出的最大元素就是所有基的异或和。那么，我们从高到低在每一位上讨论，是否存在一个基的最高位是这一位以及这一位上所有基的异或和就好了。当然要再套一个数位dp。

时间复杂度\(O(\log^2 n)\)。 

#include <bits/stdc++.h>

using namespace std;

const int N = 40, MOD = (int)(1e9 + 7);

int dp[N][N][2],len,lim[N],n,ans;

int calc(int x,int sgn) {

  if (x == 0) return sgn ^ 1;

  return 1 << x >> 1;

}

int main() {

  cin >> n;

  if (n == 0) return puts("1"), 0;

  while (n) {

    lim[++len] = n&1;

    n >>= 1;

  }

  reverse(lim+1,lim+len+1);

  dp[0][0][1] = 1;

  for (int i = 0 ; i < len ; ++ i)

    for (int j = 0 ; j <= i ; ++ j)

      for (int k = 0 ; k < 2 ; ++ k) {

        (dp[i+1][j][k & (lim[i+1]^1)] += 1ll * dp[i][j][k] * calc(j,0) % MOD) %= MOD;

        if ((!k) || lim[i+1]) {

          (dp[i+1][j][k] += 1ll * dp[i][j][k] * calc(j,1) % MOD) %= MOD;

          (dp[i+1][j+1][k] += dp[i][j][k]) %= MOD;

	}

      }

  for (int i = 0 ; i <= len ; ++ i)

    (ans += (dp[len][i][0] + dp[len][i][1]) % MOD) %= MOD;

  printf("%d\n",ans);

  return 0;

}

小结：关键也就在于线性基可以通过高斯消元避免重复。算是涨知识了。

【做题】CF388D. Fox and Perfect Sets——线性基&数位dp的更多相关文章
  1. BZOJ CF388D. Fox and Perfect Sets [线性基 数位DP]

    CF388D. Fox and Perfect Sets 题意:求最大元素\(le n\)的线性空间的个数 给神题跪了 orz 容易想到 每个线性基对应唯一的线性空间,我们可以统计满足条件的对应空间不 ...

  2. 数位DP CF388D - Fox and Perfect Sets

    题目地址 一个整数perfect集合满足性质:集合中随意两个整数的异或和仍在这个集合中. 求最大数不超过K的perfect集合的个数. 每一个集合都是一个线性的向量空间. .能够通过全然的高斯消元得出 ...

  3. codeforces 388D Fox and Perfect Sets（线性基+数位dp）

    #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define mp mak ...

  4. Codeforces 388 D. Fox and Perfect Sets

    $ >Codeforces \space 388 D.  Fox and Perfect Sets<$ 题目大意 : 定义一个完美的集合 \(S\) ,当且仅当 \(S\) 非负非空,且 ...

  5. Codeforces 1299D - Around the World（线性基+图论+dp）

    Codeforces 题目传送门 & 洛谷题目传送门 一道线性基的综合题 %%%%%% 首先注意到"非简单路径""异或和"等字眼,可以本能地想到线性基. ...

  6. bzoj 3811: 玛里苟斯【线性基+期望dp】

    这个输出可是有点恶心啊--WA*inf,最后抄了别人的输出方法orz 还有注意会爆long long,要开unsigned long long 对于k==1,单独考虑每一位i,如果这一位为1则有0.5 ...

  7. Codeforces Round #460 (Div. 2) B Perfect Number（二分+数位dp）

    题目传送门 B. Perfect Number time limit per test 2 seconds memory limit per test 256 megabytes input stan ...

  8. Codeforces 388D Fox and Perfect Sets

    链接:CF388D 题目大意 给定一个数\(n\),求选择\(0 \sim n\)中任意个数的数字组成的集合\(S\)中,有多少满足若\(a\in S,b\in S\),则\(a \bigoplus ...

  9. HDU 5863 cjj's string game ( 16年多校10 G 题、矩阵快速幂优化线性递推DP )

    题目链接 题意 : 有种不同的字符,每种字符有无限个,要求用这k种字符构造两个长度为n的字符串a和b,使得a串和b串的最长公共部分长度恰为m,问方案数 分析 : 直觉是DP 不过当时看到 n 很大.但 ...

随机推荐
  1. RocketMQ的使用

    1 在resources目录下创建config目录,新建文件rocketmq.properties文件 # 指定namesrv地址 suning.rocketmq.namesrvAddr=localh ...

  2. HDU 1087 最长不下降子序列 LIS DP

    Nowadays, a kind of chess game called “Super Jumping! Jumping! Jumping!” is very popular in HDU. May ...

  3. C++中位运算

    简介 1 位逻辑运算符: & (位   “与”)  and ----------------- 2个都为1 才是1-----------0^0 = 0 , 0^1 = 0,  1^0 = 0  ...

  4. 详解tween.js 中文使用指南

    补间(动画)是一个概念,允许你以平滑的方式更改对象的属性.你只需告诉它哪些属性要更改,当补间结束运行时它们应该具有哪些最终值,以及这需要多长时间,补间引擎将负责计算从起始点到结束点的值. 例如,pos ...

  5. 找不到System.Web.Optimization命名空间

    找不到System.Web.Optimization命名空间,无法完成BundleConfig.cs内容的添加. 解决方法如下:打开程序包管理控制台,在控制台中输入:Install-PackageMi ...

  6. javascript（二）：数据类型&数值

    第一部分:数据类型 javascript数据类型通常来说是6种(ES6新增第七种Symbol类型) number:数值 string:字符串 boolean:布尔类型,true或false undef ...

  7. tensorflow学习5----GAN模型初探

    生成模型: 通过观测学习样本和标签的联合概率分布P(X,Y)进行训练,训练好的模型能够生成符合样本分布的新数据,在无监督学习方面,生成式模型能够捕获数据的高阶相关性,通过学习真实数据的本质特征,刻画样 ...

  8. 102.自己实现ArrayList

    package collection; import java.util.ArrayList; import java.util.List; /** * 自己实现一个ArrayList,帮助理解底层结 ...

  9. JustOj 2039: 成绩排名 （结构体排序）

    题目描述 每次期末考试成绩出来之前的一段时间大豪哥心里都是痛苦的,总感觉自己会在班上排名特别差.所以当成绩出来以后大豪哥想快点知道班上的总排名,以便知道自己的排名.(PS:大豪哥班上有个学霸名叫日天, ...

  10. Autel MaxiSys Pro MS908P Software Update Gudie

    This article aims to guide on how to update software for Autel MaxiSys Pro. (Suitable for MaxiDiag E ...

相关阅读

目录[+]