First of all. Forgive my poor English .......
288A - Polo the Penguin and Strings
Just arrange "abababa..." greedy ,and then "cdef..." . Note the condition of k=1
288B - Polo the Penguin and Houses
for array [k+1 ... n] , the answer is pow((n-k),(n-k)). Because for every last n-k position, there are n-k choices.
for [1 .. k], my solution is DP.DP[k] stands for the number of valid conditions for p[2..k], without considering p[1]. Supposing that we erase the last entry p[k], then there may x's items that point to 1 directly or indirectly, and k -2 -x point to k directly or indirectly.
So DP[k] is sum(dp[x] * dp[k-1-x] * C(k-2,x)) for every x that fits 0 <= x <= k — 2 . So for [1..k] the answer is dp[k] * k. because p[1] can be any positive number that no greater than k.
288C - Polo the Penguin and XOR operation
It's so easy for problem C ... We list every number S from N to 1. Supposed that S is a n-bit binary number [bn-1 .. b0] that bn-1 is 1 , find a n-bit binary number [cn-1 ... c0] = X that X xor S = pow(2,n) — 1, then we shouldn't consider X any more ..
288D - Polo the Penguin and Trees
We can use tree DP to solve this: Let the node 1 be the root . {path u} can stand for all paths whose node which is closest to root is u . (That is to say, these nodes' LCA is u)
For node u, we can count all {path {v that is not in the subtree of u}} that not intersect with {path u} easily . It's C(2, n — number of nodes in u's subtree (short for sum(u))) .
for v in u's subtree . Supposing we have known the number of {path v}. we want to know the number of path that belongs to {path u} and not intersects with u. we can calculate all the paths that both belong to u and v. supposing u's son is S0 ... Sm-1, v belong to Si the answer for v is path(u)-(sum(u)-sum(Si))*sum(v) . Is it easy :) ? for all v in Si , the answer is sum(Si)*path(u)-(sum(u)-sum(Si)) * sumsum(Si); It's easy to calculate every node's sumsum and sum .
for v , path(v) = sum(sum(Si) * (sum(u)-sum(Si)-1)) + sum(u)-1; It's easy too , Isn't it ? :)
288E - Polo the Penguin and Lucky Numbers . ans(l..r) = f(r)-f(l).
if we know the answer of f(b[0...m-1]) it's not hard to calculate b[0...m], b[m] = 4 or 7
f(b[0...m-1]) = a0 * a1 + a1 * a2 + ... an-1 * an (a0 = '444...44') there are m's 4.
so b[0 .. m] = (a0*10+4) * (a0 *10 + 7) + (a0 * 10 + 7) * (a1 * 10 + 4) + .....
there are two parts: (ai * 10 + 4) + (ai * 10 + 7) for i = (0 .. n) is equal to 100 * ai * ai + 110 * ai + 28
we should know sum^2(ai) and sum(ai)
another part is (ai * 10 + 7) * (ai+1 * 10 + 4) is equal to 100 * (ai * ai+1) + 70 * ai+1 + 40 * ai + 28 for i = (0... n) if b[m] = 7 for i = (0... n-1) if b[m] = 4
It's hard to explain all the details and I'm too tired :( Bye!