正文 

当前位置： 首页 > 技术 > java教程

codeforces631d.dreamoonlikessequences位运算^组合数递推(代码片段)

mzrong mzrong     2023-04-05     421

关键词：

https://codeforces.com/contest/1330/problem/D

给出d,m, 找到一个a数组，满足以下要求：

a数组的长度为n,n≥1;

1≤a1<a2<?<an≤d；

定义一个数组b：b1=a1, ∀i>1,bi=bi−1⊕ai ，并且b1<b2<?<bn−1<bn；

求满足条件的a数组的个数并模m；

人话：求一个a数组满足递增，并且异或前缀和也递增 ，求出a数组个数mod m。

太菜了，不会，看了很多题解才会的，这里总结一下：

参考官方题解 https://codeforces.com/blog/entry/75559

首先思考数组递增并且前缀异或和也递增(异或运算：不进位加法 1^1=0,1^0=1,0^0=0)，那么就必须满足后面一个数二进制的最高位1的位置大于前面一个数的二进制的最高位1的位置，我们来看下为什么，假如最高位和前一个相同，那么前缀异或和最高位的1就消掉了，肯定会变小，最高位比前一个低，那这个数就比前一个数小了，不满足数组递增，所以要比前一个数的最高位高。

每个数1的最高位 h(ai)=v, v代表ai的最高位，例如：h(1)=0,h(2)=h(3)=1, and h(4)=h(7)=2.

找出每个最高位的个数，例如 h(ai)=v，ai的最高位为v，找到最高位为v的区间，[2v,2(v+1)−1] ,还要注意一个边界问题，不能大于d，所以为：[2v,min(2(v+1)−1,d)],那么个数就为 min(2(v+1)−1,d)-2v+1，最后再加上不选的一种情况，最后为min(2(v+1)−1,d)-2v+1+1。然后分组，把最高位相同的分在一起，每一次都从一个组里面选择一个数或者不选，来组成a数组，就是把每个最高位的个数都乘起来（不选的情况我把它算进最高位的个数里面了），再减掉全部不选的情况，就好了。

例如：d=6,最高位为0的有1个，那么我们有两种选择，选1或者不选；最高位为1的有2个，那么我们有三种选择，选2或者3或者不选，最高位为2的有3个，那么我们有四种选择，选4或者5或者6或者不选；然后组合在一起，里面有全部不选的一种情况，所以最后结果要减1，即：2*3*4-1=23.

 写得很啰嗦，因为我看了好久才看懂 ~~

技术图片 
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int mod=1e9+7;
typedef long long ll;
//typedef __int128 LL;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;

int main()

    int t;
    scanf("%d",&t);
    while(t--)
    
        ll d,m;
        scanf("%lld%lld",&d,&m);
        ll ans=1;
        for(int i=0;i<=32;i++)
        
            if(d<(1<<i))break;
            ans=(ans*(min(d,(1ll<<(i+1))-1)-(1<<i)+1+1))%m;
        
        ans--;
        if(ans<0)ans+=m;
        printf("%lld
",ans);
    
    return 0;
View Code

 还有一种递推的方法，参考博客：https://www.cnblogs.com/AaronChang/p/12635428.html

用一个cnt[i]数组来记录每个最高位的个数，每次选择了一个数之后就从后面的数中选择；

dp[i]表示二进制的最高位1在前i位（包含第i位）的方案数之和，dp[i]=dp[i-1]+dp[i-1]*cnt[i]+cnt[i] ,（只单独取cnt[i]也可以）

技术图片 
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int mod=1e9+7;
typedef long long ll;
//typedef __int128 LL;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3f;
ll dp[40],cnt[40];
int main()

    int t;
    scanf("%d",&t);
    while(t--)
    
        ll d,m;
        scanf("%lld%lld",&d,&m);
        ll a=d,idx=0,t=1;
        while(a)
        
            cnt[++idx]=min(d-(t-1),t);//下标从1开始，方便dp数组
            t<<=1;
            a>>=1;
        
        for(int i=1;i<=idx;i++)dp[i]=((dp[i-1]+(dp[i-1]*cnt[i])%m)%m+cnt[i])%m;
        printf("%lld
",dp[idx]);
    
    return 0;
View Code

 

 

 

 

codeforces-631b水题

注意到R和C只与最后一个状态有关/*HEAD*/structnode2{intkind,las,val,pos;node2(){}node2(intk,intl,intv,intp){kind=k;las=l;val=v;pos=p;}}b[maxn];boolcmp(node2a,node2b){returna.las<b.las;}intmt[5003][5003];intmain(){ 查看详情

codeforces631(div.2)e.drazillikesheap贪心(代码片段)

https://codeforces.com/contest/1330/problem/E有一个高度为h的大顶堆：有2h-1个不同的正整数，下标从1到2h−1，1<i<2h,a[i]<a[⌊i/2⌋].现在我们要降低堆的高度，为h，有2g-1个整数，那么我们要删掉2h-2g个数；选择索引i删除，... 查看详情

codeforces631d.dreamoonlikessequences位运算^组合数递推(代码片段)

https://codeforces.com/contest/1330/problem/D给出d,m,找到一个a数组，满足以下要求：a数组的长度为n,n≥1;1≤a1<a2<?<an≤d；定义一个数组b：b1=a1, ∀i>1,bi=bi−1⊕ai ，并且b1<b2<?<bn−1<bn；求满足条件的a... 查看详情

unabletoconnecttocupsserverlocalhost:631

Q1：启动samba时，在日志上提示： tail -f /var/log/samba/log.smbdUnable to connect to CUPS server localhost:631解决办法：在smb.conf中修改print字段load printers = nop 查看详情

projecteular631

代码丢家里了系列................直接搜索.....每次我们考虑新来的一个数放哪例如当前序列12345你要放一个6,你可以放哪里呢162345612345123456一共三个可行解,我们怎么判断是否发生了"1243"的情况首先6肯定是那个"4",那么我们找到后面... 查看详情

西铁城cl-s631无法打印，打印测试空白

   问题描述：西铁城CL-S631无法打印突然无法打印，电脑上打印测试页时纸张输出几张空白的之后设定和错误灯同时慢闪，并伴有响声，按一下取消键声音停止，重启打印机，“设定/再印刷”(MODE/REPEAT)键，正常亮绿色... 查看详情

killetsoft.transdat.v19.631cd

 Visual.Integrity.pdf2imagve.v10.5.5.51CD 3DQuickPress.6.1.4.HotFix.Win641CD CAMWorks.2017.SP0.Win641DVD Adobe.Photoshop.CC.2017.&.CameraRaw.v9.6.1.Win32_641DVD CSTStudioS 查看详情

631分！脑瘫男孩儿考取厦大计算机系，他：圆梦了

...术分享，如有侵权，联系删除转载于：新智元631分，圆梦厦大。这个脑瘫男孩儿不曾被上帝眷顾，但他扼住了命运的咽喉，经过不懈努力，最终实现计算机求学梦。这个男孩，曾不受上帝眷 查看详情

631分！脑瘫男孩儿考取厦大计算机系，他：圆梦了

...术分享，如有侵权，联系删除转载于：新智元631分，圆梦厦大。这个脑瘫男孩儿不曾被上帝眷顾，但他扼住了命运的咽喉，经过不懈努力，最终实现计算机求学梦。这个男孩，曾不受上帝眷 查看详情

day631.判等问题-java业务开发常见错误

判等问题Hi，阿昌来也，今天学习记录的是equals、compareTo和Java的数值缓存、字符串驻留等问题展开讨论.一、equals和==的区别在业务代码中，我们通常使用equals或==进行判等操作。equals是方法而==是操... 查看详情

用matlab画直方图！急！

x=【1.471.621.531.571.631.471.631.51.531.61.561.471.61.51.631.621.531.51.591.471.471.691.51.471.561.531.561.471.51.51.481.531.61.471.531.541.561.51.531.471.561.531.541.531.591.561.571.531.51.561.561.571.591.541.561.51.51.561.581.561.541.531.51.531.471.571.561.531.561.571.541.541.51.561.531.61.531.5... 查看详情

ubuntu关闭cups服务

...10.10每次开机时使用nmap扫描127.0.0.1的时候总是能发现一个631端口开启,在/etc/services找到631端口是网络打印机服务,但对于我一个普通用户来说这根本就不需要,于是到网上去搜索,发现631端口对应的程序是cups,但是不敢卸载,因为网上... 查看详情

reportcodeforces-631c(单调栈)(代码片段)

题目链接 题目大意:给定序列,给定若干操作,每次操作将$[1,r]$元素升序或降序排列,求操作完序列 首先可以发现对最后结果有影响的序列$r$一定非增,并且是升序降序交替的可以用单调栈维护这些序列,再考虑最后如何通过... 查看详情

javascriptstringvstostring（）（http://jsbench.github.io/#df630cae631d261fd4298d5dd0b6f2e2)#jsbench(代码片

查看详情

大文件处理（上传，下载）思考(代码片段)

...传不了，文件下载时间太长，tcp直接给断开了😱😱😱等效果为了方便大家有意义的学习，这里就先放效果图，如果不满足直接返回就行，不浪费大家的时间。文件上传文件上传实现，分片上传... 查看详情

codeforces-504a&&codeforces-624c&&codeforces-2b

Points1.　关键要看到以度数为1的点作为突破口。2.　关键是发现两者不同只能是a-c，而剩余的点必须为b3.　注意0的情况。  查看详情

codeforces

1.背景可能很多人都久闻codeforces网站的大名，却苦于各种各样的区域性问题或玄学问题，没能真正地体验到cf所带来的极致魅力   2.关于codeforces Codeforces简称:cf(所以谈论cf的时候经常被误会成TX的那款游戏).网址:codeforces... 查看详情

codeforces603epastoraloddities

CodeForces603EPastoralOdditieshttps://codeforces.com/contest/603/problem/Ehttps://codeforces.com/blog/entry/21885TutorialHint存在sunnypaving的充要条件是什么题目与最小生成树有无关系我们有(n)个点,(m)条边,称每个点度数为奇数的方案为sunnypavin 查看详情