Чуть более суток назад появился пост, с ужасно оформленным вопросом о казалось бы простой задаче. Пост был заминусован, но я попытался решить задачу, и не смог этого сделать
Условие в человеческом виде выглядит примерно так:
На входе дано число n <= 200. Предположим мы выписали все n*2 значные номера(с ведущими нулями) счастливых билетов. Билет считается счастливым, если сумма первых n цифр равна сумме последних n цифр. В выходной файл нужно вывести 10 чисел — сколько раз мы написали цифру 0, цифру 1, и т.д.
В голове вроде сразу появилось ДП, но оно оказалось медленным, я уже по-разному его попереписывал, но все равно получется слишком медленно для указаных ограничений.
Может кто-нибудь из 43 человек заминусовавших автора знает как решать эту задачу?
Вот мой код
Основные тормоза здесь в строках 63-67. Может можно здесь применить быстрое умножение? Хотя для массива в 200 элементов имхо это не даст сильного ускорения, может можно придумать простую свёртку, чтобы считать это дело? Нам ведь не нужен сам результат умножения, нам нужна сумма a[i] * i, где a это многочлен dcnt в квадрате. Сейчас код работает 13 секунд, но комп у меня довольно мощный, и это многовато. Асимптотика выходит B^2 * N^3 B = 10 (основание СС).
UPD: забыл указать, что ответ нужно вывести по модулю 10^9 + 7
Не минусовал, но ты делаешь что-то слишком сложно. Посчитай арифметический треугольник dp[i][j] = число чисел длины i с суммой чисел j, для каждого индекса храним, сколько всего в нем нулей, единиц и т.д. После этого возводим аккуратно все в квадрат на N-ной строке. Вроде, профит и B^2*N^2
длинка же нужна
goo.gl_SsAhv не упоминает, что в оригинальной задаче ответ по модулю.
длинка не нужна, по модулю, забыл указать.
Но ведь у нас не получиться возвести в квадрат на N-ой строке. Давай просто для одной цифры решать, чтобы проще было. Вот есть у тебя 100500 номеров с суммой цифр 42. теперь 100500^2 это вообще не понятно что, это не ответ. Например у нас 500 номеров содержат одну нашу цифру, а остальные 100000 две цифры, тогда ответ это + (1 + 1) * 500^2 + (1 + 2) 500 * 100000 * 2 + (2 + 2) * 100000^2. Короче многочлен надо в квадрат возводить.
Не понимаю, почему не получается просто так возводить. Первая половина независима от второй. Ясно, сколько раз каждое число с заданной суммой упоминается в ответе.
Ну ты для n = 2 проверь руками, уже здесь получится жопа.
Подожди, почему вектор встречаемости не надо просто помножить на дважды количество чисел в каждом элементе?
Upd. 2 разряда сумма 4. Известно, что это 40, 31, 22, 13 и 04, т.е. 2 2 2 2 2 0 0 0 0 0. В итоге будет 25 четверок, которые 20 20 20 20 20 0 0 0 0 0, например, для 4 это "40хх" пять штук плюс "хх40" пять штук плюс "04хх" пять штук плюс "хх04" пять штук.
У меня такое решение почему-то на двойке не работало. Так и не смог его заставить работать(
Пускай набрать f[n,k] это количество способов набрать сумму k с помощью n слагаемых, тогда ответ для цифры c казалось бы 2nf[n-1, k — c]f[n, k] получается что-то вроде O(b^2n^2).
А вот это да, хороший чит :) Осталось доосмыслить почему цифра нужное число раз учтется.
ага, всё ок. просто начал сразу думать не в ту сторону, и за рамки собой же поставленой модели не мог выйти.
Ну мы фиксируем позицию и цифру и считаем сколько раз цифра встретится именно на этой позиции. Позиций 2n отсюда и множитель.
Да, так еще проще, и это O(b*n^2).
Почему? У динамики f[n, k] всего n^2 * b состояний, переход делается за b. В итоге сложность O(n^2*b^2).
Если я правильно понял, то тут еще придется просуммировать это по всем k, верно?
С другой стороны, если применить известный прием — заменить в другой половине билета все цифры x на 9 - x, то сумма цифр станет 9n и ответ будет просто 2n·f[2n - 1, 9n - c]
Кстати говоря, такие f можно посчитать методом включения-исключения за O(bn) (по модулю конечно).
Кстати, кому интересно, эта задача с недавно прошедшей областной олимпиады в Казахстане. Правда там ограничения не такие там 1 <= n <= 100 :)
И почти все писали прекалк.
Я ни одного прекалька не видел. ACube предлагал такое решение: посчитаем обычную динамику для счастливых билетов, т.е dp[i][j] = количество чисел длины i и суммой цифр j. Затем решаем для каждой цифры отдельно: зафиксируем ее позицию, от текущей суммы отнимаем нашу цифру и домножаем на количество в другой половинке билета.
UPD: Было уже такое решение, оказывается
У меня был прекалк, так как динамика dp[i][j][k][z] — количество чисел длины i с суммой цифр j, и цифра k встречается z раз работала на макс. тесте около минуты.
Можно решить динамикой. Решаем для каждой цифры отдельно : dp[cur][sum] -> ответ для нашей задачи, если сумма первых cur цифр равно sum, при этом цифры от 0 .. n — 1 берем со знаком +(plus), а цифры от n .. 2 * n — 1 cо знаком -(minus).
cnt[cur][sum] -> количество таких состояний.
Асимптотика O(B ^ 2 * N ^ 2) , где B = 10 здесь код
8-9 числа у нас по Казахстану проходила областная олимпиада, присутствовала данная задача с ограничением N<=100. Здесь текст моего измененного кода для N<=200.