致命漏洞

【问题描述】                                              

魔法学家Rutherford.D.Imbalance最近发表了一个生成伪随机序列的方法：

B_0=1

B_(n+1)=2B_n                ,2B_n<2^T

B_(n+1)=(2B_n xor X) mod 2^T  ,2B_n>=2^T

其中X和T给定。

他使用这个方法来构造他研制的式神的神经指令加密系统，可是作为Synophia大陆稀有的以研究数学为工作的你的好友Lwins_Alpha，敏锐地发现了这个方法存在着致命的漏洞。其中最严重的问题莫过于可以通过一些数学手段快速计算得这个序列的任意一项。Lwins_Alpha本想写信告知Imbalance这个问题，但是她突然发现Imbalance不可能看懂她的复杂的数学符号，于是她向你——以扫地为生来隐藏自己真实身份的大陆有史以来最伟大的式神制造师——Lwins_***求助了。(***为待定内容，视你最后提交上来的文件包而定)

为了证明Imbalance生成伪随机序列的方法确实有致命漏洞，最简单的方法莫过于编写一个能快速计算B_n的式神，然后将它邮寄给Imbalance。而在式神的其他部分都由你的徒弟Lwins_Lights编写的情况下，你只需要使用Pascal/C/C++语言编写最核心的部分——输入n,T,X，输出B_n：因为Lwins_Alpha为了考验你的IQ，居然没有告诉你快速计算B_n的具体方法！

不能让她小瞧你，抱着这样的信念，你开始了自己的工作。

【输入格式】

输入文件bug.in共三行，每行一个正整数，分别为n,T,X。

【输出格式】

输出文件bug.out仅包含一个正整数B_n。

【输入样例】

7

7

7

【输出样例】

    7

【数据约定】

对于20%的数据：n<=10^ 5, T<=20。

对于55%的数据：n<=10^5。

对于100%的数据：n<=10^30, T<=100, 0<X<2^T。

看到题目的瞬间我晕了，xor是什么，度娘说是异或，经过程序验证，AxorB！=A+B，希望全部破灭

暴力先打吧，程序附上：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int b[1000000];
int n,T,X,k;
int main()
{
   int i,j,t,a,c,d;
   for (j=1;j<=100;j++){
   cin>>n>>T>>X;
   b[0]=1; k=1;
   t=1;
   for (i=1;i<=T;i++)t*=2;
   cout<<"t:"<<t<<endl;
   cout<<"B[0]:1"<<endl;
   for (i=1;i<=n;i++)
    {
       if (k*2<t) {cout<<"2B["<<i<<"]<t";
                    b[i]=2*k;}
                   else{a=2*k;
                        c=a^X;
                        b[i]=c%t;
                        cout<<"2B["<<i<<"]>=t";
                    }
       k=b[i];
       cout<<"               B["<<i<<"]:"<<b[i]<<endl;
    }
}
   return 0;
}