POJ 3652 Persistent Bitsシンプル文字列シミュレーション
http://poj.org/problem?id=3652
Persistent Bits
Time Limit: 1000 MS
メモリLimit: 65536 K
Description
What Next Software creates sequence generators that they hope will produce fairly random sequences of 16-bit unsigned integers in the range 0–65535.In geneal a sequence is specifed by ingers A B， C，and S，where 1≦ A < 32768,0≦ B < 65536,2≦ C < 65536,and 0≦ S < C. S is the first element(the) seed）of the sequence，and each later element is generated from the previous element.IfX is an element of the sequence，then the next element is
(
A *
X +
B)%
C
where'%is the remander or modulus operation.Although everelement of the sequence will be a 16-bit unsigned integer less than 65536,the intermediate reult A * X + B may be larger，so calculations shuld be done with a 32-bit 要点 rather than a 16-bit ショート？ト to ensure accurate reults.
Some values of the parameters produce better sequences than others.The most embarrasing sequences to What Next Software re re re re one or more bits.A bitat never changes throughot the sequence persistent.Ideally，a sequence will haveのpersistent bits.Your job is to test a sequence and determine which bits are persistent.
For example、a particularly bad cholice is A = 2, B = 5, C = 18,and S = 3.It produces the sequence 3，(2*3+5)%18=11，(2*11+5)%18=9，(2*9+5)%18=5，(2*5+5)%18=15，(2*15+5)%18=17,then(2*17+5)%18=3 again，and the the the the the the the the the the the。
Decimal
16-Bit Binary
3
0000011
11
000000000 1011
9
0000000001
5
000000000 0101
15
000000000 1111
17
0000010001
オーバーオール
0000001
The last line of the table indicates which bit positions are always 0、always 1、or take on both values in the sequence.Note that 12 of the 16 bitare are persistent.（Good randm sequens will persistine the the the extrence） A = 1, B = 1, C = 6400,and S=0 hasのpersistent bits，but it's also not randowm:it just counts from 0 to 63999 before repeat.) Note that a sequence does not need to return to the seed:with A = 2, B = 0, C = 16,and S = 2，the sequence goes 2，4，8，0，0，0，…
Input
The e e e are from one to sixteen datasets followed by a line containing only 0.Each dataset is a line containing decimal integer values for A，B，C，and S，separated by single blanks.
Output
The e e e e is one line of output for each data set、each containing 16 characters、ether'1'、'0'、or'for each of the 16 bitts in order，with the most significant bit first，with'1'indicating the corelding bit is always 1，'0'meaning the corese ponding bit is always 0，and'indicating the bit taes on values of both 0 and 1 in the sequence.
Sample Input
2 5 18 3
1 1 64000 0
2 0 16 2
256 85 32768 21845
1 4097 32776 248
000000000000????1
????????????????
000000000000???0
0101010101010101
0???000011111??? WA /* Author : yan
* Question : POJ 3652 Persistent Bits
* Data : Tuesday, December 21 2010
*/
#include<stdio.h>
#define bool _Bool
#define true 1
#define false 0
int bit[16];
int bit_cache[16];
int bit_cnt[16];
int visited[65536];
int seed;
int s;
void Deci_to_Bin(int a)
{
memset(bit_cache,0,sizeof(bit_cache));
int _i;
int cnt=15;
while(a)
{
bit_cache[cnt--]=a%2;
a/=2;
}
//for(_i=0;_i<16;_i++) printf("%d",bit_cache[_i]);
//printf("/n");
}
bool have_visited(int a)
{
int _i;
if(a==s) return true;
for(_i=0;_i<seed;_i++)
if(a==visited[_i])
return true;
return false;
}
int main()
{
freopen("input","r",stdin);
int a,b,c;
int tmp,i;
int pos;
while(scanf("%d",&a)&&a!=0)
{
seed=0;
scanf("%d %d %d",&b,&c,&s);
visited[seed++]=s;
if(s==0)
{
Deci_to_Bin(c-1);
for(i=0;i<16;i++)
if(bit_cache[i]==1)
{
pos=i;
break;
}
for(i=0;i<pos;i++) printf("%d",bit_cache[i]);
for(i=pos;i<16;i++) printf("?");
printf("/n");
continue;
}
Deci_to_Bin(s);
for(i=0;i<16;i++) bit[i]=bit_cache[i];
tmp=s;
memset(bit_cnt,0,sizeof(bit_cnt));
while(1)
{
tmp=(a*tmp+b)%c;
if(have_visited(tmp)) break;
Deci_to_Bin(tmp);
for(i=0;i<16;i++)
if(bit[i]!=bit_cache[i]) bit_cnt[i]++;
visited[seed++]=tmp;
}
for(i=0;i<16;i++)
{
if(bit_cnt[i]!=0) printf("?");
else printf("%d",bit[i]);
}
printf("/n");
}
return 0;
}
， ， #include<iostream>
using namespace std;
bool flag[100001];
int wk[2][16];
int main()
{
int A=0, S=0 ,S1=0, B=0, C=0,k=16,j=0,yu=0,time=0;
while( scanf("%d",&A) && A != 0 )
{
scanf("%d%d%d",&B,&C,&S);
S1=0,k=16,j=0,yu=0,time=0;
memset(flag,false,sizeof(flag));
memset(wk,0,sizeof(wk));
if(S==0&&B==0)
{
printf("0000000000000000/n");
continue;
}
while(flag[S]!=true)
{
k=15;
time++;
yu=S;
while(yu!=1&&yu!=0&&time==1)
{
wk[0][k--]=yu%2;
yu/=2;
wk[0][k]=1;
}
S1=(A*S+B)%C;
k=15;
yu=S1;
if(S1==0)
{
if( B == 0 )
{
break;
}
for(j=0;j<16;j++)
wk[1][j]=0;
}
if(yu==1)
{
for(j=0;j<16;j++)
wk[1][j]=0;
wk[1][15]=1;
}
while( yu!=1 && S1 != 0 )
{
wk[1][k--]=yu%2;
yu/=2;
wk[1][k]=1;
}
flag[S]=true;
for(j=15;j>=0;j--)
{
if(wk[0][j]!=wk[1][j])
{
wk[1][j]=100;
}
}
for(j=0;j<16;j++)
wk[0][j]=wk[1][j];
S=S1;
if(time==63999)
break;
}
for(j=0;j<16;j++)
{
if(wk[1][j]==100)
{
cout<<"?";
continue;
}
cout<<wk[1][j];
}
cout<<endl;
}
return 0;
} http://hi.baidu.com/wklove123/blog/item/4123bfcc1883205a0fb34594.html ， ， AC！！！