まず、wを昇順でソートする。 dp[i][j] = #{w[i]以降のみを使って和がjとなる組} sum[i] = w[i]までの和 とするとき、次の3つの場合を考えれば良い。(i) w[0]を使わない (ii) w[0]からw[i]までを使い、w[i+1]を使わない(0 (iii) 全て使う(i)の場合, (i=1,j) …

組(X,Y)(X f(X) = 2X or S - 2Xこれをmod S で見ると、f(X) ≡ 2X or -2X であるから、f^K (X) ≡ 2^K * X or -2^K * Xf^K (X) ≡ -2^K * X は個数がS - 2^K * X の場合に対応するから、X = min(A,B)として、min(2^K * X, S - 2^K * X) (mod S) が答えとなる。 …