Problem:


Problem F: Find the Multiples

You are given a sequence a0a1...aN-1 digits and a prime number Q. For each i ≤ j with ai &ne; 0, the subsequence aiai+1...aj can be read as a decimal representation of a positive integer. Subsequences with leading zeros are not considered. Your task is to count the number of pairs (i, j) such that the corresponding subsequence is a multiple of Q.

Input

The input consists of at most 50 datasets. Each dataset is represented by a line containing four integers N, S, W, and Q, separated by spaces, where 1 ≤ N ≤ 105, 1 ≤ S ≤ 109, 1 ≤ W ≤ 109, and Q is a prime number less than 108. The sequence a0...aN-1 of length N is generated by the following code, in which ai is written as a[i].

    int g = S;
    for(int i=0; i<N; i++) {
        a[i] = (g/7) % 10;
        if( g%2 == 0 ) { g = (g/2); }
        else           { g = (g/2) ^ W; }
    }

Note: the operators /, %, and ^ are the integer division, the modulo, and the bitwise exclusiveor, respectively. The above code is meant to be a random number generator. The intended solution does not rely on the way how the sequence is generated. 

The end of the input is indicated by a line containing four zeros separated by spaces.

Output

For each dataset, output the answer in a line. You may assume that the answer is less than 230.

Sample Input

3 32 64 7
4 35 89 5
5 555 442 3
5 777 465 11
100000 666 701622763 65537
0 0 0 0

Output for the Sample Input

2
4
6
3
68530

In the first dataset, the sequence is 421. We can find two multiples of Q = 7, namely, 42 and 21.

In the second dataset, the sequence is 5052, from which we can find 5, 50, 505, and 5 being the multiples of Q = 5. Notice that we don't count 0 or 05 since they are not a valid representation of positive integers. Also notice that we count 5 twice, because it occurs twice in different positions.

In the third and fourth datasets, the sequences are 95073 and 12221, respectively.



Sample input:
3 32 64 7
4 35 89 5
5 555 442 3
5 777 465 11
100000 666 701622763 65537
0 0 0 0


Sample output:
2
4
6
3
68530

Submission status: Accepted

Solution code:
from collections import defaultdict

def gen(N, S, W):
    g = S
    for i in range(N):
        yield (g//7) % 10
        if g % 2 == 0:
            g //= 2
        else:
            g = (g//2) ^ W

def solve():
    N, S, W, Q = map(int, input().split())
    if N == 0:
        return False
    bs = list(gen(N, S, W))
    ans = 0
    if Q == 2 or Q == 5:
        cnt = 0
        for i in range(N):
            b = bs[i]
            if b != 0:
                cnt += 1
            if b % Q == 0:
                ans += cnt
    else:
        rev10 = pow(10, Q-2, Q)
        D = defaultdict(int)
        D[0] = 1
        s = 0; v = 1
        first = 1
        for i in range(N):
            b = bs[i]
            if first and b == 0:
                continue
            s = (s + v * b) % Q
            v = v * rev10 % Q
            ans += D[s]
            if i < N-1 and bs[i+1] != 0:
                D[s] += 1
            first = 0
    print(ans)
    return True

while solve():
    ...

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+9
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n,s,w,q):
        g = s
        a = []
        for i in range(n):
            a.append(g // 7 % 10)
            if g % 2 == 1:
                g = (g // 2) ^ w
            else:
                g //= 2
        if q % 2 == 0 or q % 5 == 0:
            r = 0
            t = 0
            for c in a:
                if c > 0:
                    t += 1
                if c % q == 0:
                    r += t
            return r
        b = [0] * (n+1)
        k = 1
        for i in range(n-1,-1,-1):
            b[i] = (b[i+1] + a[i] * k) % q
            k = k * 10 % q
        d = collections.defaultdict(int)
        r = 0
        for i in range(n):
            if a[i] > 0:
                d[b[i]] += 1
            r += d[b[i+1]]

        return r

    while 1:
        n,m,l,o = LI()
        if n == 0:
            break
        rr.append(f(n,m,l,o))

    return '\n'.join(map(str, rr))


print(main())