В этой задаче все очевидно: если все цифры счастливы и сумма первых n / 2 равна сумме последних n / 2, то ответ YES, иначе - NO. Все это можно сделать одним проходом циклом по номеру и одной проверкой.

Можно увидеть, что ответ на задачу не будет превосходить никогда 1777777. Поэтому, все что нужно сделать это написать какую-то функцию F(x), которая бы возвращала маску числа x. После этого нужно просто написать такой код:

x = a + 1;

while (F(x) не равно b)

увеличить x на 1;

После этого в x будет содержаться результат.

Найдем два числа: c47 (количество таких позиций i строки, что a_i = 4, b_i = 7), c74 (количество таких позиций i строки, что a_i = 7, b_i = 4). Результатом после этого будет, очевидно, число max(c47, c74) (так как min(c47, c74) операций пойдут на обмен цифр, а остальные - на переключения цифр).

Пусть у нас есть какой-то результат в виде строки s. Давайте удалим из нее все повторы, то есть пока есть два одинаковые символы рядом, один из них удалим. На F(47) и F(74) такое, очевидно, не повлияет. Тогда в такой строке 4 и 7 будут чередоваться. При этом видно, что |F(47)-F(74)| ≤ 1. Поэтому, если |a₃ - a₄| > 1, то результату не существует. Иначе нам нужно перебрать возможные "корни" (строчки после выполнения выше упомянутой операции удаления одинаковых цифр) результата, по которым нужно построить результат. Если a₃ = a₄, то корней возможных есть два: строчка вида 474747474...474 или 74747474...747 (подогнана по размеру под a₃). Если a₃ < a₄, то корнем будет строчка вида 747474...7474, иначе, если a₃ > a₄, то корень - 47474747...4747. При этому количество блоков 47 и 74 нужно делать ровным a₃ и a₄, соответственно.

Теперь нужно по корню построить результат. Но перед тем нужно проверить, не превышает ли количество 4 в корне a₁, а количество 7 - a₂. Если так, то результата не существует. Иначе нам нужно доставить какое-то количество 4 и 7, которых не хватает корню. Очевидно, что для сбережения лексикографической минимальности, все 4 нужно доставить рядом с первым вхождением цифры 4 в корень, а 7 - рядом с последним вхождением 7. На a₃ и a₄ это, конечно, не повлияет.

Как всем, наверное, известно, счастливых чисел на промежутке [1;10⁹] есть 1022. Воспользуемся этим фактом для решения задачи. Пусть C[i] - сколько раз i-е счастливое число встречается в массиве a. Теперь заведем ДП (динамическое программирование) с параметрами DP[pos][cnt] - сколько существует подмножеств из всех счастливых цифр массива таких, что в них использованы только счастливые до pos-го, а размер подмножества ровен cnt. DP[0][0], очевидно, ровно 1. Если мы в каком-то стане DP[pos][cnt], то можно не взять pos-е счастливое число вообще. То есть DP[pos+1][cnt] += DP[pos][cnt]. Если же мы возьмем pos-е счастливое число, то сделать это можно С[pos] способами, то есть DP[pos+1][cnt+1] += DP[pos][cnt]*C[pos].

Теперь нужно найти полный результат. Для этого переберем количество счастливых чисел в подмножестве, пусть это i. Тогда это число нужно еще домножить на C(count_unlucky, k - i) (биноминальный коэффициент), где count_unlucky - количество не счастливых чисел массива. Суммой по всем таким i и будет результат.

Также в этой задаче нужно не забывать все аккуратно брать по простому модулю 10⁹ + 7, а для вычисления бин. коэффициентов нужно использовать обратный элемент в кольце по модулю.

В основе решения стоит тот факт, что количество счастливых чисел до 1000. Давайте решим такую задачу: у нас есть массив из 1000 элементов, каждый до 1000. Нужно найти количество таких пар промежутков, что-бы у них не было одинакового числа. Для этого давайте зафиксируем i - левую границу правого промежутка. Теперь будет перебирать j от i до n - 1 и поддерживать множество чисел из промежутка [i;j]. Очевидно, что время-от-времени в это множество (пусть это будет S) будут добавляться числа, при этом каждое новое ровно один раз. Тогда если у нас в множество додается какое-то число, нам нужно посмотреть на все вхождения этого числа на промежутке [0;i - 1]. Если есть такое вхождение k (k < i), то не может быт такого левого хорошего промежутка (для правого [i;j]) [l;r], что l ≤ k и k ≤ r. По этому мы можем использовать set и каждое из приходящих вхождений закидывать в set, поддерживая количество хороших левых промежутков (таких что в этом промежутке нет ни одного числа из set), для этого пригодиться функция S.lower_bound сета. 

А теперь у нас между этими числами есть еще и числа, на которые смотреть вообще не нужно (у нас это несчастливые числа). Если фиксировать только такие i что a[i] счастливое и перебирая j (j > i) только такие, что a[j] - счастливые то нам можно за O(n² * logn) найти таким методом количество таких пар, что правый промежуток содержит хотя бы одно счастливое число. Теперь еще нужно количество таких пар, что правый промежуток не содержит счастливых. Для этого переберем i - левую границу правого промежутка, a[i] - не счастливое. Пусть f(i) - минимальное j, (j > i) и a[j] - счастливое. Тогда у нас есть f(i) - i способов поставить правую границу правого промежутка (так что-бы не содержал счастливого). А левый промежуток может быть любим - способов это сделать есть i * (i + 1) / 2 (нумерация с 0).

Давайте решим задачу деревом отрезков. Будем держать такие числа в каждой вершине дерева:

n4 - количество цифр 4 на промежутке.

n7 - количество цифр 7 на промежутке (на самом деле n7 = length - n4, то для наглядности будем использовать и n7).

n47 - размер максимальной неубывающей подпоследовательности на промежутке.

n74 - размер максимальной невозрастающей подпоследовательности на промежутке.

Тогда когда мы делаем "switch", то для нужных вершин делаем просто swap(n7, n4), swap(n47, n74). Для каждой вершины дерева мы должны поддерживать эти числа: n4(father) = n4(left_son) + n4(right_son), n47 = max(n47(left_son) + n7(right_son), n4(left_son) + n47(right_son), n4(left_son) + n7(right_son)). Результатом для запросов count тогда будет n47 корня дерева.

Для большей информации о дереве отрезков читайте прекрасную статью от paladin8.