papamitra https://blog.hatena.ne.jp/papamitra/ papamitra https://papamitra.hatenadiary.org/ AtCoder AtCoder ABC ABC#132 DP AtCoder 600点 累積和 F - Small Products 問題 正の整数K個を一列に並べたものであって、隣接して並んでいるどの2つの整数の積もN以下であるものの個数を109+7で割った余りを求めてください。 解説 公式解説にあるようにxが最後の整数となるようなi個の整数を並べて条件を満たす場合の数dp[i][x]を使ったプログラムをまず書いてみる。 const MOD: i64 = 1000000000 + 7; fn solve(n: usize, k: usize) -> i64 { let mut dp = vec![vec![0i64; n + 1]; k + 1]; for i in 1..(n + 1… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpapamitra.hatenadiary.org%2Fentry%2F2019%2F07%2F15%2F135922" title="AtCoder ABC #132 F - Small Products - papamitra" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20O%28NK%29 Hatena Blog https://hatena.blog 2019-07-15 13:59:22 rich https://papamitra.hatenadiary.org/entry/2019/07/15/135922 1.0 100%