1 henucm

尚未进行身份认证

那就再努力一点吧

等级
TA的排名 2w+

2019牛客暑期多校训练营(第九场)I KM and M

传送门思路:因为最后按位与的是一个常数,所以只需要看这个常数对应为1的位置,在M、2M、3M...NM这N个数字中,有多少个仍然是1。用个数乘以对应位的2的幂次即可。那么现在问题变成了如何求这个个数。我们考虑对于一个数字iM,如果求它二进制下第j位是否是0。显然,我们可以先把iM右移j位得到x,然后再把iM右移j+1位得到y,再把y左移1位得到z,z-x的值即为iM第j位的数值。而这个过程,就...

2019-08-22 17:37:05

好看的桌面壁纸网站

Wallhaven:https://alpha.wallhaven.cc/Unsplash:https://unsplash.com/Pexels:https://www.pexels.com/Desktopography:http://desktopography.net/huaban:https://huaban.com/wallpapermaiden:https://www....

2019-08-22 13:40:57

数论 二次剩余模板

来自憨批的博客(2k图片加载有点慢需要耐心等待)附带证明对于如果存在x使得≡nmodP则称n是模P意义下的二次剩余structT{longlongp,d;};longlongKsm(longlonga,longlongb,longlongp){longlongres=1;while(b)...

2019-08-22 10:47:17

2019牛客暑期多校训练营(第九场) B Quadratic equation (二次剩余)

传送门题意:给你b,c,p=1e9+7,满足以下方程的x,y,如果没解输出-1-1(x+y)modp=b(x*y)modp=c思路:已知x+y=b或x+y=b+p,xy=c+kp;则通过二次剩余定理,求出(x-y)x=(x-y)+(x+y)>>1y=x+y-x;#i...

2019-08-22 10:42:41

2019牛客暑期多校训练营(第八场)J.Just Jump (思维DP)

传送门题意:某人要从1走到L点,中间有L-1个点可以走,他每次最少走d步。有m个条件,在第ti步不能走到pi点。问有多少种走法。思路:大佬博客#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=1e7+1234;constintMOD=99...

2019-08-21 15:18:15

2019牛客暑期多校训练营(第七场) I Chessboard

传送门题意:给你一个N,M,然后你可以任意构造一个k*k的矩阵,使得矩阵内每个元素最少是M,且任意不同行不同列的k个元素总和不超过N且都相同,问有多少种构造方法。思路:解释:我们枚举k,我们可以把每个元素减去M,那么就相当于N减去k*M,简化问题并且不影响答案解释:构造两个矩阵Ai,Bi对于这两个矩阵,我们可知他们前面的系数和为T则满足结果等...

2019-08-19 15:39:08

__int 128 大数读入读出模板

voidscan(__int128&x)//输入{x=0;intf=1;charch;if((ch=getchar())=='-')f=-f;elsex=x*10+ch-'0';while((ch=getchar())>='0'&&ch<='9...

2019-08-19 13:57:00

2019牛客暑期多校训练营(第五场) C generator 2 【BSGS算法】

传送门题意:已知x[i]=(a*x[i-1]+b)%p,求满足等式的x数组的下标,且该下标小于n。若不存在则输出-1。思路:1.x0==v,直接输出02.a==0(1)v==x0输出0(2)v==b输出1(3)否则输出-13.a==1式子就可以化简成xn=x0+nbmod...

2019-08-16 17:38:50

bzoj2242 [SDOI2011]计算器

传送门题意:1、给定y、z、p,计算y^zmodp的值;2、给定y、z、p,计算满足xy≡z(modp)的最小非负整数x;3、给定y、z、p,计算满足y^x≡z(modp)的最小非负整数x。思路:第一问是裸的快速幂第二问,因为P是质数,所以求一下乘法逆元再乘z就行了,特判y是p的倍数时无解第三问,bsgs模板#include<iostrea...

2019-08-16 10:10:48

poj 2417 【BSGS算法】

传送门题意:A^x=B(modC)(C是质数),都是整数,已知A、B、C求x。思路:先把x=i*m-j,其中m=ceil(sqrt(C)),(ceil是向上取整)。这样原式就变为A^(i*m-j)=B(modC),再变为A^j×B=A^(m*i)(modC)。枚举j(范围0-m),将A^j×B存入hash表枚举i(范围1-m),从hash表中寻找第一个满足A^...

2019-08-15 10:59:40

2019牛客暑期多校训练营(第二场)B Eddy Walker2 【杜教BM】

传送门题意:一个人从0点出发,在数轴上向右走,每次有1/K的概率向右走1步,有1/K的概率向右走2步,…,有1/K的概率向右走K步问到达Ni点的概率是多少注:Ni==-1时,代表Ni在无穷远处思路:①Ni==-1,也就是无穷远处考虑走一步能走的距离的期望是,那么由于期望的性质,不妨认为每步都走那么看能不能到达N,就等价于看是从0,1,....

2019-08-14 14:34:23

2019牛客暑期多校训练营(第三场) G Removing Stones

传送门题意:给定N,表示N堆石子,每堆石子数为a[],问多少个区间,可以满足“石子总和若为偶数,那么可以两两取来自不同堆的石子,直到取完;如果为奇数,那么排除其中一个,然后可以两两取来自不同堆的石子,直到取完”。等价于求有多少个长度不小于2的连续子数列,使得其中最大元素不大于所有元素和的1/2.#include<iostream>#include<cmath>...

2019-08-14 09:04:51

期望的线性性(可加性)【CodeForces280c】【bzoj3036】【bzoj2134】

...好像题有点古老了bzoj那道都不见了都没法去交了只好贴别人的代码了大佬博客Codeforces280c题意给出一棵含n个白点的有根树,每次随机选择一个还没有被染黑的节点,将这个节点和这个节点子树中的所有点染黑.问期望操作多少次后所有点都被染黑.N<=100000思路只有删除掉1号点才算结束。考虑一个点被选中删除的概率。,dep[i]表示i点的...

2019-08-13 14:43:01

BZOJ4318 期望的线性性质

先看一道和这道类似的题目描述某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:(我们来简化一下这个游戏的规则:有次点击要做,成功了就是o,失败了就是x,分数是按comb计算的,连续a个comb就有分,comb就是极大的连续o。比如ooxxxxooooxxx,分数就是Sevenkplus闲的慌就看他打了一盘,有些地方跟运...

2019-08-12 17:46:56

2019牛客暑期多校训练营(第一场)H xor

题意:对于所有异或和为0的子集大小加和思路:像这种异或和的我们就考虑用线性基来做,因为要求的是子集大小的总和,那我们就对于每一个数来说,来计算他的贡献。首先我们用n个数建立一个线性基a1,如果这n个数都用上了,那就说明不可能有子集异或和为0,否则,如果有r个用上了,剩下了n-r个,那就说明剩下的数都能用基内的数表示,对于没用上的数x来说,他能和外面的数搭配方案有2^(n-r-1)中,因此对于...

2019-08-12 09:00:29

洛谷P4839 P哥的桶 线段树+线性基

传送门题意:N个操作,第K个桶放一个X,查询L到R区间的桶任意数的异或最大值。#include<iostream>#include<algorithm>#include<cmath>#include<cstdio>#include<cstring>#definelllonglongusingnamespac...

2019-08-09 13:02:12

2019牛客暑期多校训练营(第四场) B xor 线性基求交+线段树

传送门大佬题解#include<iostream>#include<cstring>#include<cmath>#include<cstdio>#include<algorithm>#definelllonglongusingnamespacestd;typedefunsignedintuint;...

2019-08-07 17:44:00

51Nod 1244 莫比乌斯函数之和 分块+Hash表

传送门大佬博客很详细#include<iostream>#include<cstring>#include<cmath>#include<cstdio>#include<algorithm>#definelllonglongusingnamespacestd;constintmaxn=4641590...

2019-08-06 11:07:40

2019牛客暑期多校训练营(第五场)G 暴力枚举+蔡勒公式

题意:T(T<=10)组样例,每次给出n(n<=1e5)个形如CABJ/AI/AC的只有'A’到‘J’之间字母构成的日期,思路:合理分配0-9的全排列,使其依次对应‘A’到'J’之间的字母,使得分配后,n个日期都合法所谓合法,这里是指满足基本日期限制条件下,年在[1600,9999]间,且该天为星期五星期五的约束条件很严格,用蔡勒公式判,每次判几个就能把不合法的判掉。...

2019-08-05 21:06:56

2019牛客暑期多校训练营(第五场)B generator 1 十进制矩阵快速幂

传送门题意:给你x0、x1a、b、mod,根据求出思路:​用十进制设为res则可得我们再设就是分解n为每一位,再去相乘。例如讲计算出来的即可#include<iostream>#include<algorithm>#include<cmath>#include<cstdio>#incl...

2019-08-05 16:03:14

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。