コンテスト中の考察 $ dp[i] でi桁目までで完結する合法な払い方の数を考える $ dp[i] はi桁未満の位jでお釣りを発生させると$ dp[j-1] 通りの支払いパターンがあるはず $ O(N^2)で求まるはず 実際には完結する桁数を決めるのが難しくできなかった 解説の解法 上の桁から考える $ i桁目が終わった時点で残りは$ |X| \lt A_…