555.1

今の難易度の状態で全部解けたら最後のSRMにしよう。

255

0と1からなる文字列を、5のべき乗の文字列に分割するとき、可能な最小の個数を求めよ、という問題。

5のべき乗の文字列を一通り用意しておいてDPやるだけ。ダイクストラでもなんでもいいけど。

555

行単位のフリップと列単位のフリップを指定された回数行った後、裏になっている個数が指定された数になっているのは何通りか答えよ、という問題。

奇数回フリップした行の数と列の数から、裏になっている個数は分かる。後は行と列について独立に、フリップ回数と全体の数と奇数回フリップされた数からパターンを求めるだけ。

全体の数から奇数回フリップされた行の割り当ては何通りか分かる。フリップ回数と奇数回フリップされた行の数から、2回フリップが発生した回数は分かる。この回数を全体に対して重複を許して割り当てる方法が何通りか、というのを求めてやる。どっちも組み合わせ。

1055

見てない。