guo deng
BAN USERWe could use Inclusion–exclusion principle AND dynamic programming. The time complexity can be reduced to polynomial.
Firstly, Inclusion–exclusion principle:
Define F(s, p) to be the no. of expressions whose result are divisible by number p. For example, F("011", 2) = 6, F("011", 3) = 3.
Define F(s, {p, q}) to be the no. of expressions whose result are divisible by at least one of the digit prime in {p, q}.
Then, by Inclusion–exclusion principle, F(s, {p, q}) = F(s, p) + F(s, q) - F(s, p * q)
We have F(s, {2, 3, 5, 7}) = F(s, 2) + F(s, 3) + F(s, 5) + F(s, 7) - F(s, 2 * 3) - ... + F(s, 2 * 3 * 5) + ... - F(s, 2 * 3 * 5 * 7)
Now, we use dynamic programming to find F(s, p).
let s[i:]be the suffix string start at index i,
let n be the length of string s.
let num[i:j] be the number converted from substring s[i:j] inclusive.
Define R[i][j] be the no. of expressions which are formed from substring s[i:] and the remainder is j while mod p. (0 <= i < n, 0 <= j < p)
For example, s = "011", p = 2, R[1][0] is the no. of expressions formed from substring "11" and the remainder is 0 while they mod 2. R[1][0] = 2, since (1 + 1) % 2 = 0, (1 - 1) % 2 = 0, and R[1][1] = 1, since 11 % 2 = 1.
R[i][j] can be calculated from sub-problems R[k][l], where (num[i:k -1] + l) % p == j or (num[i: k - 1] - l) % p == j, for all k > i and k < n.
Then R[i][j] = Sum(R[k][(j - num[i:k - 1]) % p] +R[k][(num[i:k - 1] - j) % p], k = i + 1, ..., n - 1)
We get F(s, p) from R[0][0].
Here is code:
int F(const string& s, int p) {
int n = s.size(), R[n][p];
memset(R, 0, sizeof(R));
for (int i = n - 1; i >= 0; i--) {
int first = s[i] - '0';
for (int k = i + 1; k < n; k++) {
for (int j = 0; j < p; j++) {
// -1 % 2 = -1 replaced with (2 + -1 % 2) % 2 = 1
R[i][j] += R[k][(p + (j - first) % p) % p];
R[i][j] += R[k][(p + (first - j) % p) % p];
}
first = 10 * first + s[k] - '0';
}
R[i][first % p] += 1;
}
return R[0][0];
}
int walprimes(const string& s) {
return F(s, 2) + F(s, 3) + F(s, 5) + F(s, 7)
- F(s, 2 * 3) - F(s, 2 * 5) - F(s, 2 * 7) - F(s, 3 * 5) - F(s, 3 * 7) - F(s, 5 * 7)
+ F(s, 3 * 5 * 7) + F(s, 2 * 5 * 7) + F(s, 2 * 3 * 7) + F(s, 2 * 3 * 5)
- F(s, 2 * 3 * 5 * 7);
}
The time complexity of F(s, q) is obviously p * n^2. Since the primes set {2, 3, 5, 7} is unchanged, the whole time complexity is only related to the length of input string which can be considered as polynomial time.
- guo deng November 08, 2013