Sorry for my curiosity, I have look at your performance at both topcoder and codeforces, and the gap is so large , is there any special reason? I thought these two will be very much similar?

Aha, I have achieved my goal last night but a little pity ...when I finished coding the 1000 pionts' problem, 7 seconds left...

Oh,thanks for your message.(I'm Chinese and my poor English)

Я решил проблему зайдя чере Tunnel A

Болт пинаешь? :D ай-ай-ай:)

Будем перебирать бит (11 вариантов), в котором ксоры множеств будут отличаться. Тогда на префиксе (до этого бита) ксор будет совпадать, то есть должен быть равен 0. Имеем динамику dp[i][x][j][k] — рассмотрели i чисел, ксор на префиксе x, нужный бит в первом множестве равен j, во втором k. Тогда к ответу нужно каждый раз прибавлять dp[max(n,m)+1][0][0][1] — ну первая размерность зависит от реализации, я писал динамику вперед, так что так получилось.

У нас есть два бинарных числа, и одно должно быть меньше другого. Переберём по первому биту где они отличаются. Пускай он будет x, всё что слева от этого бита l, а справа r.

Тогда, нам необходимо, если мы выберем числа в множества и заксорим только l-части, чтобы результат был одинаковым. Или xor результатов был 0. Так как результат — сам xor. То нам надо чтобы l-части всех выбранных чисел в оба множества был 0. r-части нас не интересуют вообще. А x — в первом множества должен быть 0, а во втором 1.

Делаем ДП: a[i][l][x1][x2] — сколько способов обработать первые i чисел, чтобы xor l-частей всех выбранных чисел был l, при этом у первого множества x-часть — x1, а у второго — x2.

Обновлять можно вперёд — проталкиваем a[i][l][x1][x2] в:

• a[i+1][l][x1][x2] (не берём)
• a[i+1][l ^ (i+1).l][x1 ^ (i+1).x][x2] (берём в первую, (i+1) <= N)
• a[i+1][l ^ (i+1).l][x1][x2 ^ (i+1).x] (берём во вторую, (i+1) <= M)

Ответ: сумма a[max(N, M)][0][0][1] по всем возможным битам.

Поздравляем его с сотой победой на Topcoder! :)

Thanks anyway :)

C is not always a sub-sequence of LCS(a,b).

Good explanation is given here