悬赏+++ing
如果已经能把x xor 2x xor 3x=0转化成x and 2x=0，接下来应该比较容易了。
由于x*2=x shl 1，所以要使x and 2x=0，那么x在二进制中相邻位不能都是1，
否则左移以后在同一位上就有两个1，结果就不为0
然后，x在二进制为i位时，可以放0或者1，
对于这两种情况，由于相邻位不能都是1，所以放1时的个数就是i-2位的所有个数（默认i-1位为0）
放0时，因为不会有相邻位冲突的情况，所以个数就是i-1位的所有个数。
把两种情况合并，就是这位上的总个数。
所以f[i]=f[i-1]+f[i-2]
然后算出1位时有2种情况，就可以全部算出来了。
我当初没有发现x xor 2x xor 3x=0就是x and 2x=0啊，自己推了将近一个小时，最后还浑然不觉这是斐波那契数列。。。
为什么呈现这样的一个数列呢?
①什么时候x xor 2x xor 3x=0呢?
首先0这个奇葩数字自然满足,放到一边先.
然后我们看a xor b=0的情况,xor的特征是数字不相同则返回1,否则返回0,而两个数xor为0说明所有位都相同,即必须有a=b,有x xor 2x=3x(0也满足)
接下来我们发现是x xor 2x=x+2x
结合着程序:
Procedure doit(x:longint);
begin
if x=1 then write(1)
else begin
doit(x>>1);
write(x mod 2);
end;
end;
Var n,i,j,sum:longint;
Begin
readln(n);
for i:=1 to 1<<n-1 do begin
doit(i);
if i xor(2*i)=3*i then write(true);
writeln;
end;
End.
我们发现所有满足的数都有这个数不出现相邻的两个1[待证理论],而且貌似是充要条件.
②抓住这个特征点,进入充要性证明:
1,充分性:如果我们的字串是10,则这个字串的当层(只看这几位数字的情况)操作满足要求.
证明:10<<1=10X(注:这个X可以是若干个10),这种情况下,两者的和为11X
即[10]
+[10X]
=[11X]
(如果后面的字串也满足这个性质,则不发生进位,X保持不变;反之,如果后面的数字发生进位,则我们单看最高位的10串,一旦进位可能出现的数字个数增多的情况,xor的结果就不等于求和的结果)
若X代表的第一个数字为1,则
[10]
+[101]
=[111],一旦后面进位则数字总位数增多,所以后面也不能有进位
若X代表的第一个数字为0,则
[10]
+[100]
=[110]这样子10or100得到的就是110,也不允许后面发生进位(即第三个0不发生变化)才能够使得这三位满足10 xor 100=110
而10xor10X=11X,与和相同,同时数字不进位,亦不影响跟高位的字串,证明这个子串满足题目要求.
2,必要性(即不满足这个理论的串都是不满足题目性质的):
如果一个串是11X,则11<<1=11X(注:这个X可以是若干个10),然后我们看到11X和11的情况,不妨找到第一个11
11X
这个样子我们发现无论如何在这三位中的第二位会产生进位,而进位最多只能是1(加法进位原则)导致的结果便是0XX,
而我们11xor11x=1XX,不符要求.所以必要性得证.
③那么我们这个性质的串,在2^n-1范围内个数是多少个呢?
用f[i]表示在0~2^i-1范围内这个No_Double_One数串的个数
首先我们可以试出f[1]=2;f[2]=3;
f[i]的话,我们发现其第一位如果为1,那么这个数串第二位必须为0,这样子
f[i]就有一种10()的情况,()正好是f[i-2]填进去后的所有可能性;
而如果第一位为0,那么我们这个和f[i-2]的情况完全独立开来,它包含的个数正好是f[i-1]的个数(多一个找不到,少一个不全面).
由此有f[i]=f[i-2]+f[i-1].数列得正.程序如下:
Begin
readln(n);
for i:=1 to n do begin
read(a[i]);
if a[i]>max then max:=a[i];
end;
f[1]:=2;
f[2]:=3;
for i:=3 to max do f[i]:=(f[i-2]+f[i-1])mod Z;
for i:=1 to n do writeln(f[a[i]]);
呵呵,以前写的解题报告,顺便发出来了