あやしい4完。
No.1986 Yummy
結局、両端のパターンは3通りしかないので最悪DPでなんとかなりそう。もうちょっと突っ込んで考えると、Nが偶数のとき先手は「美味しい飴」を全部取れる。ということはNが奇数のときも同様で、先手の初手は実質1通りしかなく、その後逆の立場になって後手が全部取れる。
No.1987 Sandglass Inconvenience
Xがa, b, cのGCDの倍数なのが必要条件。十分条件にもなっているかの検証が本体。互除法が動作するかを見ると、確かに動作しそうだ。a, bのGCDが求まって、それとcのGCDも求まるか？a, bをセットで使うとGCD(a, b)の砂時計として使える。これも求まる。じゃあ、その任意の倍数が測れるか？これも、GCD(a, b, c)がセットされた砂時計とそれ以上の砂を持った別の砂時計が存在するので、測れる。怖い見た目に楽な実装ではあるが、ちょうどいい難易度の内容があってよかった。
No.1988 Divisor Tiling
ググってメルセンヌ素数とかを調べる。2冪と素数（Mとする）の積になっているのか。Mを含む側を横として、まず横の長さがMである場合を構築する。約数のうちMを含むものを横Mの長方形として配置する。残りの2冪は縦1で横に並べればちょうどMになる。へー。2冪は上に持ってきてMとペアにすれば合わせて横の長さM*2にもできる。それとM*2を合わせればM*4にもできる。つまり、横Mの長方形を構築してから、転置したり周期を変えたりすればよい。これは面白い。コンテスト中に新しいことを教えてくれるの嬉しい。
No.1989 Pairing Multiset
小さい数から貪欲にペアを作っていくのが最善（そうでないと数直線上で考えて重なりが生じるので最小にならない）。N*2個のボールにM個の仕切りを入れる。まず、iとj（i < j）がペアになる通り数を考えてみる。まあ求まりそうだけど計算量にM^2が付いてしまう。何もわからないのでとりあえずそれを実装してみるが、実装しても何もわからない。しばらく座っているだけだった。仕切りの個数毎にまとめて考えられないかとか考えて、そもそもf(S)の値も分解して仕切り1個の寄与を考えることができることに気づく。ある仕切りについて、左に奇数個（そのとき当然右にも奇数個）のボールがあるとき、答えに1だけ寄与する。奇数という制限がなければ簡単（どの仕切りにとっても状況は同じ）。ちょうど半分が奇数か？とエスパーしてみるがダメ。もう少し考えると、全体で4個のボールがあるとき左に奇数個あるのは0個から4個の5通り中2通りだ。単純にこれを実装してみるとサンプルが通って提出してAC。
writer解、なんじゃこりゃー。
