三乗の解法はすぐに出てくるので、それを上手に高速化する！ 問題へのリンク 問題概要 のグリッドが与えられる。"." マス (通路) には行けるが "#" マス (壁) には行けない。左上のマスから右下のマスへと行きたい。毎回のターンで以下のいずれかの行動をと…

AtCoder ABC 183 E - Queen on Grid (水色, 500 点)

いろんな DP が考えられそう！ 問題へのリンク editorial 問題概要 正整数 が与えらる。以下の条件を全て満たす有理数の多重集合は何種類存在するか、998244353 で割ったあまりを求めよ。 多重集合の要素数は 多重集合の要素の総和は 多重集合の要素は全て (…

AtCoder ARC 107 D - Number of Multisets (黄色, 600 点)

このセットの writer をしていました 問題へのリンク 問題概要 を並び替えてできる数列 は 通りあるが、そのうち以下の条件を満たすものが何通りあるかを、1000000007 で割ったあまりを求めよ。 を満たすような がちょうど 個 を満たすような がちょうど 個 …

CPSCO2019 Session3 F - Flexible Permutation (600 点設定)

こないだのドワンゴからの挑戦状で、分割数を用いる問題が出題されたので、周辺の話題を整理してみました。 数え上げに関する話題として分割数やスターリング数は時折登場しますが、どちらも写像12相と呼ばれる広い枠組みに含まれています。今回は分割数を、…

分割数と、問題まとめ