PKU 3652 Persistent Bits

http://poj.org/problem?id=3652
線形合同法によって出てくる乱数列のビットの出現の仕方を出力するというような問題。

最悪でも2^16ぐらいループを回して全て列挙すればよい。
シードに戻ってくるという勘違いのせいでかなりまえにTLEだったものを書き直しまいた。

bool vis[65536];

main(){
  int a,b,c,s;

  while(scanf("%d",&a),a){
    scanf("%d%d%d",&b,&c,&s);
    memset(vis,0,sizeof(vis));
    int a0=0|s,a1=(0xFFFF)&s;
    int ne=s;
    while(!vis[ne]){
      vis[ne]=true;
      a0|=ne;
      a1&=ne;
      ne=(a*ne+b)%c;
      if(a0==0xFFFF && a1==0)break;
    }
    for(int i=15;i>=0;i--){
      if(a0>>i&1 && a1>>i&1)putchar('1');
      else if(~a0>>i&1 && ~a1>>i&1)putchar('0');
      else putchar('?');
    }
    puts("");
  }
}