ICPC 2010 Problem F

#include
#include < map >
#define rep(i,a,b) for(int i=a;i<=b; i++)

using namespace std;
int N, S, W, Q;
int a[100100], m[100100];
map v;

void gene_data(){
int g=S;
rep(i,0,N-1){
a[i]=(g/7)%10;
if (g%2==0){g=g/2;}
else {g=(g/2)^W;}
}
}

void mod_process(){
m[N-1]=1;
for(int i=N-2;i>=0; i--) {
m[i]=(m[i+1]*10) % Q;
}
m[N-1]=(a[N-1]%Q);
for(int i=N-2; i>=0; i--){
m[i]=(a[i]*m[i]+m[i+1])%Q;
}
}

int cal(){
v.clear();
int sum = 0;
rep(i,0,N-1){
sum+=v[m[i]];
if (a[i]!=0) v[m[i]]++;
if ((m[i]==0)&(a[i]!=0)) sum++;
}
return sum ;
}

int main(){
freopen("F.in","r",stdin);
freopen("F.ans.txt","w",stdout);
int sum, c0;

for(;;){
sum = 0;
c0 = 0;
cin >> N >> S >> W >> Q;
if ((N==0)&(S==0)&(W==0)&(Q==0)) return 0;

gene_data();

if (Q==2) {
rep(i,0,N-1){
if (a[i]==0) {
c0++;
sum+=i+1-c0;
}
else {
if (a[i]%2==0) sum+=i+1-c0;
}
}
cout << sum << endl ;
continue;
}

if (Q==5) {
rep(i,0,N-1) {
if (a[i]==0) {
c0++;
sum+=i+1-c0;
}
else {
if (a[i]==5) sum +=i+1-c0;
}
}
cout << sum< continue;
}

mod_process();
cout << cal() << endl;
}
return 0;
}