koba-e964 https://blog.hatena.ne.jp/koba-e964/ koba-e964の日記 https://koba-e964.hatenablog.com/ こういうのはかなり得意だと思っている。 No.802 だいたい等差数列 - yukicoder 問題 以下の条件を満たす長さNの整数列Aの個数を数え、10^9+7で割った余りを求めよ。 1 i = 1, ..., N - 1に対して D1 制約 2 1 0 解法 まず愚直DPを考える。DP[i][j] := (Aの第i項まで見たとき、A[i]=jとなるような数列の個数)としたとき、以下のような遷移を持つDPを行えばよい。 init: DP[1][j] = 1 step: DP[i + 1][j + k] += DP[i][j] (D1 これのDP[N][1] + ... DP[N][M]が答え… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkoba-e964.hatenablog.com%2Fentry%2F2019%2F03%2F18%2F000751" title="yukicoder No.802 だいたい等差数列 - koba-e964の日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2019-03-18 00:07:51 rich https://koba-e964.hatenablog.com/entry/2019/03/18/000751 1.0 100%