关键词:
51nod 1310:Chandrima and XOR
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1310
题目大意:序列$S={1,2,4,5,...}$,其中任何一个数转为二进制不包括两个连续的$1$。给出一个长度为$N$的正整数数组$A$,$A_1, A_2,...,A_n$记录的是下标(下标从$1$开始)。求$S[A_1]$ Xor $S[A_2]$ Xor $S[A_3]$ ..... Xor $S[A_n]$的结果.
dp
用$dp[i]$维护$i$位二进制数不包括两个连续的$1$的所有数,然后对每个$A_i$迭代求出$S[A_i]$的$1$所在的位.
代码如下:
1 #include <cstdio> 2 #include <algorithm> 3 #define N 91 4 using namespace std; 5 typedef long long ll; 6 const ll p=1000000007; 7 ll n,a[N],dp[N],x; 8 ll mul(ll a,ll b){return a*b%p;} 9 ll powmod(ll x,ll n){ 10 ll r=1; 11 while(n){ 12 if(n&1)r=mul(r,x); 13 x=mul(x,x); 14 n>>=1; 15 } 16 return r; 17 } 18 void init(){ 19 dp[1]=1; 20 for(int i=2;i<N;++i) 21 dp[i]=dp[i-1]+dp[i-2]+1; 22 } 23 int main(void){ 24 init(); 25 scanf("%lld ",&n); 26 while(n--){ 27 scanf("%lld",&x); 28 while(x){ 29 ll idx=lower_bound(dp,dp+N,x)-dp; 30 a[idx]^=1; 31 x-=dp[idx-1]+1; 32 } 33 } 34 ll ans=0; 35 for(int i=0;i<N;++i)if(a[i]) 36 ans=(ans+powmod(2,i-1))%p; 37 printf("%lld ",ans); 38 }
51nod1185||51nod1072威佐夫博弈
贴个模板:平常的跟高精度java的;int:#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<iostream>#include<cstdio>#include<cmath>#include<string>#include<queue>#include<alg 查看详情
51nod1631小鲨鱼在51nod小学
...题鲨鱼巨巨2.0(以下简称小鲨鱼)以优异的成绩考入了51nod小学。并依靠算法方面的特长,在班里担任了许多职务。 每一个职务都有一个起始时间A和结束时间B,意为小鲨鱼在[A,B]时间内,担任了某职务(inclusively)。 现在... 查看详情
51nod1354:选数字
51nod1354:选数字题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1354题目大意:有$T(Tleqslant20)$组数据,每组给出$n(nleqslant1000)$个数和$K(Kleqslant100,000,000)$,问在这$n$个数中选取若干个,积为$K$的方案数有多少.DP+离散化与... 查看详情
[51nod]配对
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1737求出树的重心,跑spfa#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<string>usingname 查看详情
51nod1232:完美数
51nod1232:完美数题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1232题目大意:如果一个数能够被组成它的各个非$0$数字整除,则称它是完美数。例如:$10$,$11$,$12$,$101$都是完美数,但是$13$就不是完美数(因为$13$不能... 查看详情
51nod2576
题意51nod做法令(f_n,d)为(d)层,目前维宽度为(n)(f_n,d=sumlimits_i=1^nf_i,d-1(n?i+1)^k)构造矩阵转移,上三角对角线相等矩阵,快速算就完了题外话一遍过qwq 查看详情
51nod1728
题意51nod做法要是想不到树就删号重练吧令(F_k)为深度不超过(k)的森林个数的EGF不超过(k)的森林,就是若干棵不超过(k)的树,取掉树的根,就是不超过(k-1)的森林就有(F_k=e^xF_k-1) 查看详情
51nod1773a国的贸易
51nod1773http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1773 #include<cstdio>#include<map>#definegcgetchar()constintmod=1e9+7,inv2=(mod+1)>>1;inta[1<<21],b[ 查看详情
51nod1241:特殊的排序
51nod1241:特殊的排序题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1241题目大意:给出$n$个数($1leqslanta_ileqslantn$),现在要对这个数组进行排序,在排序时只能将元素放在数组的头部或尾部,问至少需要移动多少个... 查看详情
51nod1537分解
题目传送门:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1537神犇题解传送门:http://blog.csdn.net/qingshui23/article/details/52350523证明好巧妙,给跪OTZ题目的式子:${left({1{ m{+}}sqrt2} ight)^{ m{n}}}$,设其 查看详情
51nod1406:与查询
51nod1406:与查询题目链接:http://www.51nod.com/onlineJudge/submitDetail.html#!judgeId=222358题目大意:给出$n$个数,问这$n$个数与$x$做位与($&$)后值为$x$的有多少个.DP显然暴力是不行的.由题目可得,若$a&x=x$,则$x$的二进制表示中为$1... 查看详情
51nod1227平均最小公倍数
传送门 查看详情
51nod1294:修改数组
51nod1294:修改数组题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1294题目大意:将一个序列修改成严格递增序列,最少需要替换几个数.dp这道题相当巧妙.最小的满足条件的序列为${1,2,3,...,n}$,若$a_i<i$那么该数必须... 查看详情
莫比乌斯函数之和51nod-1244(杜教筛)
莫比乌斯函数之和 51Nod-1244 题意: 查看详情
51nod1428活动安排问题
51Nod 1428 活动安排问题Link: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428 1428 活动安排问题基准时间限制:1 秒空间限制:131072 KB分值: 10 难度:2级算法题有若干个活动,第i 查看详情
51nod1616最小集合
51nod1616最小集合题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1616题目大意:若$a$和$b$均在集合$S$中,则$gcd(a,b)$也在$S$中。现给出$S$中$n$个元素,问$|S|$的最小值.数论定义$f(k)$为这$n$个数中能被$k$整除的数的个数.对... 查看详情
51nod1640mst+二分
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=16401640天气晴朗的魔法题目来源:原创基准时间限制:1秒空间限制:131072KB分值:20难度:3级算法题收藏关注这样阴沉的天气持续下去,我们不免担心起他的健康。 51nod魔法学校... 查看详情
51nod1230:幸运数
51nod1230:幸运数题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1230题目大意:如果一个数各个数位上的数字之和是质数,并且各个数位上的数字的平方和也是质数,则称它为幸运数。例如:120是幸运数,因为120的数字... 查看详情