这个题刚开始是看错题了。。一点思路都没有
到后来把题目看对了以后，有一点思路，但还是不会做。。无奈只能看官方题解
官方题解是这样的：
First convert number k into binary number system. If some bit of k is 0 than the result of or opertion applied for every adjacent pair of those bits in array a must be 0, that is no two adjacent those bits in array a are 1. We should count how many times this is fulfilled. If the values were smaller we could count it with simply dpi = dpi - 1 + dpi - 2, where dpi is equal to number of ways to make array od i bits where no two are adjacent ones. With first values dp1 = 2 and dp2 = 3, we can see that this is ordinary Fibonacci number. We can calculate Fibonacci numbers up to 1018 easily by fast matrix multiplication. If some bit at k is 1 than number of ways is 2n — \t{(number of ways bit is 0)}, which is also easy to calculate. We must be cearful for cases when 2l smaller than k (solution is 0 then) and when l = 63 or l = 64. Total complexity is
.
看了以后大概懂了他的思路。将每一二进制位看成一步，则根据乘法原理，总方案数=每一位的方案数的积。
如果k的某一位二进制值为零，则发现每个相邻元素不能均为1.然后dp即可，是斐波那契数列，矩阵乘法O(log n) 无压力
如果k的某一位二进制值为1，则必然存在两个相邻元素的值为1，然后发现f[n]=2^(n-1)+f[n-1] 答案为2*f[n-1]，然而这个式子让人很不爽。考虑到这是计数类问题，从反面考虑，则方案为2^n-dp[n]( dp[n]是指某一二进制位为零时其取值 ），然后就爽了。。
注意如果2^l<=k的话直接输出零就可以
update：附提交记录(各种奇葩错误秀脑洞QAQ
这个题写了一上午我会乱说？
转载于:https://www.cnblogs.com/tsingyawn/p/4576322.html