首页 > 代码库 > 51nod 1310：Chandrima and XOR
51nod 1310：Chandrima and XOR
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",&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\n",ans);38 }
51nod 1310：Chandrima and XOR
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。