解説 区間DPです。 dp[l][r]:= [l, r)の部分列の回文の数とすると、 dp[l][r] += dp[l + 1][r] + dp[l][r-1] - dp[l+1][r-1] に加えて、s[l] == s[r-1]なら dp[l][r] += dp[l+1][r-1]+1 です 計算量は 提出コード #include <iostream> #include <string> #include <sstream> #include <stack> #</stack></sstream></string></iostream>…

問題リンク 解説 式変形すると となります。とは互いに素であるので、の素因数をとのどちらかに押し付けます あとは拡大ユークリッド互除法を用いれば、差が1でかつ最小になるようなものを求められます 提出コード atcoder.jp