yukicoder No.260 世界のなんとか3
なんか結果が合わなくて解ききる前に寝てしまった。
解法
見た目から明らかに桁DPです。
dp[n][big][exist][mod3][mod8] = (n番目までで,元の数より大きいフラグがbigで,とある桁に3があるかのフラグがexistで,3で割った余りがmod3で,8で割った余りがmod8であるような場合の数)
を更新していきます。
最近わかったのですが,桁DPは次の状態を表すnext_existとかnext_mod3とか新しい変数を用意してやるとかなり書きやすくなりますね。
const int MAXN = 100100; const int MOD = 1e9+7; int mod10[MAXN]; int dp[MAXN][2][2][3][8]; // big 3exist mod3 mod8 ll calc(const string& s) { memset(dp, 0, sizeof(dp)); int N = s.size(); dp[0][0][0][0][0] = 1; for (int n = 0; n < N; n++) for (int flag = 0; flag < 2; flag++) for (int e = 0; e < 2; e++) for (int m3 = 0; m3 < 3; m3++) for (int m8 = 0; m8 < 8; m8++) { if (dp[n][flag][e][m3][m8] == 0) continue; if (flag == 0) { int num = s[n]-'0'; for (int i = 0; i < num; i++) { // bigは1 int nm3 = (m3 + i) % 3; int nm8 = (m8 + i * mod10[N-1-n]) % 8; int ne = e; if (i == 3) ne = 1; (dp[n+1][1][ne][nm3][nm8] += dp[n][flag][e][m3][m8]) %= MOD; } // bigは0 int nm3 = (m3 + num) % 3; int nm8 = (m8 + num * mod10[N-1-n]) % 8; int ne = e; if (num == 3) ne = 1; (dp[n+1][0][ne][nm3][nm8] += dp[n][flag][e][m3][m8]) %= MOD; } else { for (int i = 0; i < 10; i++) { // bigは1 int nm3 = (m3 + i) % 3; int nm8 = (m8 + i * mod10[N-1-n]) % 8; int ne = e; if (i == 3) ne = 1; (dp[n+1][1][ne][nm3][nm8] += dp[n][flag][e][m3][m8]) %= MOD; } } } ll ans = 0; for (int flag = 0; flag < 2; flag++) for (int e = 0; e < 2; e++) for (int m3 = 0; m3 < 3; m3++) for (int m8 = 1; m8 < 8; m8++) { if (m3 == 0 || e == 1) (ans += dp[N][flag][e][m3][m8]) %= MOD; } return (ans % MOD); } int check(const string& s) { int sum = 0; int n = s.size(); int tmp = 0; if (n < 3) tmp = stoi(s); else tmp = stoi(s.substr(n-3, 3)); if (tmp % 8 == 0) return 0; for (int i = 0; i < n; i++) { if (s[i] == '3') return 1; sum += (s[i]-'0'); } if (sum%3 == 0) return 1; return 0; } int main() { cin.tie(0); ios::sync_with_stdio(false); string A, B; cin >> A >> B; mod10[0] = 1; for (int i = 1; i < MAXN; i++) mod10[i] = (mod10[i-1]*10) % 8; ll ans = calc(B) - calc(A) + check(A); ans %= MOD; if (ans < 0) ans += MOD; cout << ans << endl; return 0; }