SRM 555 - Codeforces

12 лет назад, # |

← Rev. 3 →

-20

сраная 555, понятно что делать, ну с*ка, пока напишешь эти 100500 динамик

→ Ответить

Dmitry_Egorov

12 лет назад, # ^ |

+15

100500=1? Да и та — предподсчитать C(n,k).

→ Ответить

12 лет назад, # ^ |

можешь рассказать это решение?

→ Ответить

Dmitry_Egorov

12 лет назад, # ^ |

Предподсчитаем все цешки до 3100на3100. Далее переберем двумя циклами сколько столько строк инвертировали нечетное число раз (пусть их a, всего строк n) и сколько столбцов инвертировали нечетное число раз (пусть их b, всего строк m). Тогда несложно увидеть, что число единичек в таблице ровно a*(m-b)+b*(n-a). Если это число совпало с S, а числа Rcount-a и Ccount-b четные неотрицательные, то к ответу надо добавить C(n,a)*C(n+(Rcount-a)/2-1,(Rcount-a)/2)*C(m,b)*C(m+(Ccount-b)/2-1,(Ccount-b)/2). Разбираем что это такое — C(n,a) — это мы выбрали какие строки будут "нечетными", на их обслуживание надо сразу же потратить a преобразований над строками. Теперь у нас осталось Rcount-a преобразований над строками и они идут парами, т.к. теперь уже все строки должны быть инвертированы четное число раз. Причем эти пары можно раскидывать как угодно. Перешли к стандартной задаче разбить число (Rcount-a)/2 на n целых неотрицательных слагаемых. Это число способов равно в точности C(n+(Rcount-a)/2-1,(Rcount-a)/2). Остальные два сомножителя — аналогичные для столбцов. Вот и все.

→ Ответить

12 лет назад, # ^ |

спасибо за объяснение, но я уже сам решил только цшками... однако, не самая лучшая идея, писать сразу, что пришло в голову на контесте

→ Ответить

1a1a1a

12 лет назад, # ^ |

расскажыте свою идею неС-шками

→ Ответить

12 лет назад, # ^ |

← Rev. 8 →

+12

честно говоря это треш, но все же тоже зашло: понятно что нужно разбить r_count на h слагаемых и c_count на w, причем, если среди h слагаемых ровно i четных, а среди w слагаемых j четных, то единиц будет i(w - j) + j(h - i)

научимся считать следуещее: количество разбиений числа n на m слагаемых, что среди слагаемх ровно p четных (понятно, остальные m - p нечетные)

будем делать это так: посчитаем динамику even[x][y] — количество разбиений числа x на у слагаемых, что все y слаегаемых четные, а так же динамику odd[x][y] — количество разбиений числа x на у слагаемых, что все y слаегаемых нечетные, понятно, как считать эту динамику: $\text{[math]}$

odd[x][y] считается аналогично

заведем теперь динамику f[p] — количество способов разбить n на m слагаемых, что среди слагаемх ровно p четных

$\text{[math]}$

и действительно, это количество разбиений в котором $p$ четных чисел, которые в сумме дают i, а остальная сумма набирается нечетными слагаемыми. C_m^p берется из того, что мы на какие-то p мест поставим четные числа, на остальные m - p мест нечетные

теперь мы имеем два массива f_row и f_column, теперь надо пробежать по (i, j) — количество четных элементов в строке и столбце (в разбиении строки и столбца на слагаемые) если i(m - j) + j(n - i) = s прибавим к ответу f_row[i]·f_column[j]

PS. от дурной головы, рукам покоя нет, вот это все писал

→ Ответить

1a1a1a

12 лет назад, # ^ |

по крайней мере у вас есть своя и правильная идея..не то, что у других — отсутствие каких либо идей ;)

→ Ответить

NotImplemented

12 лет назад, # ^ |

Красиво.

→ Ответить

12 лет назад, # ^ |

Эм? Там все через цшки считается

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

-14

ну это таргеты может через цшки все там считают, а в моей комнате много решений (подавляющее большинство), как и у меня, это >=2 динамик

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

+24

Ну так тогда может не задача виновата?

Вон в харде вообще 2 принципиально разных решения в зависимости от "ширины программы" — и я не жалуюсь

→ Ответить

Dmitry_Egorov

12 лет назад, # ^ |

В свете результатов систестов хотелось бы узнать как решался хард.

→ Ответить

12 лет назад, # ^ |

А можно тогда поподробнее пожалуйста, про второй тип решения ради интереса?

Я придумал но не успел накодить, что сделав backtracking перебрав конечные позиции и получив строку из '0', '1' и '?' (что угодно), если их меньше половины (потому что диапазон движения бегунка больше половины), то катит inclusive-exclusive, а если их больше половины, то диапазон движения меньше половины, и следовательно вопросительных знаков меньше половины и катит перебор с set'ом.

→ Ответить

12 лет назад, # ^ |

Ну да, либо включение-исключение, либо полное построение, это и есть те 2 принципиально разных решения

И насчет бактракинга я не понял — мы просто с каждой позиции берем момент, когда последний раз строка могла быть валидной

→ Ответить

Edvard

12 лет назад, # ^ |

А как быстро включение исключение считать?

→ Ответить

12 лет назад, # ^ |

Да вроде бы должно проходить и 2^18 * 18 * 36. На всякий можно было попробовать чуть уменьшить границу для включений.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Проходит и так. У меня под завязочку как раз — 1.3 с одной стороны и 1.6 с другой. То есть было бы хотя бы 37 ограничение — пришлось бы оптимизить

А, ну и границу для включений у меня не получилось бы уменьшить еще и из-за МЛ

→ Ответить

Edvard

12 лет назад, # ^ |

А откуда число 18 взялось?

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Потому что если различных масок > 18, то это значит, что число вопросительных знаков в каждой маске не больше чем 18, и вместо включений можно делать перебор с сетом.

→ Ответить

Edvard

12 лет назад, # ^ |

Добавил тупой перебор если масок много и прошло в практисе. Жаль мог на СРМе сдать первый "настоящий" хард

→ Ответить