The relationship between Byteland and Bitland ison thin ice and a war is certained to start. The message of your agent shows that the communication in Bitland is encrypted. They've chosen three different RNGs that can produce a sequence of 0s and 1s. At the start of every day, they'll randomly pick one RNG, pick one random seed and use that RNG to generate a binary sequence of length 2000. This sequence will act as an encryption key. As an officer of Byteland, rather than decrypt the datas, you've decided to solve an easier problem first: for an encyption key generated, figure out which RNG is used to generate it. The following is a sample code of these three RNGs written in the out-dated language, C++ : typedef unsigned int u32;
The relationship between Byteland and Bitland is on thin ice and a war is certained to start. The message of your agent shows that the communication in Bitland is encrypted. They've chosen three different RNGs (Random Number Generators) that can produce a sequence of 0s and 1s. At the start of every day, they'll randomly pick one RNG, pick one random seed and use that RNG to generate a binary sequence of length 2000. This sequence will act as an encryption key. As an officer of Byteland, rather than decrypt the datas, you've decided to solve an easier problem first: for an encyption key generated, figure out which RNG is used to generate it. The following is a sample code of these three RNGs written in the out-dated language, C++ (it's recommend to copy-paste the following code to your favorite editor): typedef unsigned int u32; typedef unsigned long long u64; struct RNG { virtual void srand(u32 seed)=0; virtual bool gen()=0; }; struct RNG0: RNG { u32 x; void srand(u32 seed) {x=seed;} bool gen() { x=x*214013u+2531011u; return (x>>28)&1; } }; struct RNG1: RNG { int index; u32 mt[624]; void srand(u32 seed) { mt[0]=seed; index=624; for(int i=1;i<624;++i) mt[i]=1812433253u*(mt[i-1]^(mt[i-1]>>30))+i; } void twist() { for(int i=0;i<624;++i) { u32 y=(mt[i]&0x80000000u)+ (mt[(i+1)%624]&0x7fffffffu); mt[i]=mt[(i+397)%624]^(y>>1); if(y&1) mt[i]^=0x9908b0df; } index=0; } bool gen() { if(index>=624) twist(); u32 y=mt[index]; y^=y>>11; y^=(y<<7)&2636928640u; y^=(y<<15)&4022730752u; y^=y>>18; ++index; return (y>>16)&1; } }; struct RNG2: RNG { u64 x; void srand(u32 seed) {x=seed;} bool gen() { x^=x<<13; x^=x>>7; x^=x<<17; return (x>>16)&1; } }; RNG *rng[3]={new RNG0(),new RNG1(),new RNG2()};
标签： HBC26276数字串 思维RNGs题解
