Solution for Codeforces Round 157

Link: http://codeforces.com/blog/entry/6213

[problem:259A]

Obviously, the only correct rows are rows WBWBWBWB and BWBWBWBW. Only thing you need to do is to check whether each string is one of these. If yes then print YES, else print NO.

[problem:259B]

Since each number is less than or equal to 10⁵, you can loop all possible a_1, 1 values, the rest of cells can be calculated from this.

[problem:258A]

It's pretty easy to notice that you need to delete the first (from the left) 0-digit. The only catchy case is 111...111 — here you need to delete any of 1-digits.

[problem:258B]

First of all, lets think about the problem of finding array c_i — the number of integers from 1 to m such, that the number of lucky digits is equal to i. It's pretty standart dynamic programminc problem, which can be solved with state [position][less][count].

It can be solved directly using DP, but to simplify a bit you can use brute froce (recursion) to brute all possible assignments of numbers of lucky digits in for all paries (up to 9 digits). Now you can divide all parties in several indepentent groups, each of which should contain the same number of lucky digits. Consider that the party of Litte Elephant is with number 1. Than assignment for the first position should have more digits than the sum of the rest (because of the statement). Since all groups are indepented (because there is no number that can have different number of lucky digits, obviously) you can find the number of resulting assignments for each group and find the final result by multiplying these all numbers and taking modulo 10⁹ + 7.

Consider that you have group of size t, each number of which should contain l lucky digits. That it's pretty easy to understand that the number of assignment is equal to (c_l)  (c_l - 1)  (c_l - 2)  ...  (c_l - t + 1).

[problem:258C]

The complexity of the possible solution is O(n  sqrt(n)  log(n)). You can see that statementlcm(b₁, b₂, ..., b_n) = max(b₁, b₂, ..., b_n) is equal to statement "All the numbers b₁, b₂, ..., b_n must divide max(b₁, b₂, ..., b_n)". You can iterate that max(b₁, b₂, ..., b_n), let it be equal to m. Find all divisors of m and sort them - p₁, p₂, ..., p_k. For each i between 1 and k you can find (using simple DP) the number of numbers a_j that p_i ≤ a_j < p_i + 1 (if i = k than p_i + 1 = max(a₁, a₂, ..., a_n) + 1), denote it asq_i. Then the reuslt is equal to 1^q₁  2^q₂  3^q₃  ...  p^q_p, because for each of the q₁ numbers there is 1 way to assign, for each of q₂ numbers there is 2 ways of assignments, and so on. But you should notice that if doing this problem in such way, you need to garantee that there is some i such b_i = m. Hance you need from the last multiplier (p^q_p) subtract (p - 1)^q_p - all the ways that there is no number equal to m.