AOJ 2326 Number Sorting
解法
dp[i] = (A+i 番目の数字から始まる数列の数) とします。B-A <= 10^5 なので, dp[i] をそこそこ早く求められれば, これでいけます。
例えば 792 という数字の次に来るものを考えると,
- 8**, 9** となるもの i.e. [800, 1000)
- 79* となるもの i.e. [793, 800)
というように, 各桁を 1 以上あげたもの(ただし 7"9"2 の 9 は 1 あげるとダメになるので無視)と
- 792* i.e. [7920, 10000)
- 792** i.e. [79200, 100000)
というように, 792 の後ろに なにかを付け加えるタイプ
の 2 通りしかありません。sum[i] = [i, B] における dp[j] の和というのをメモしておけば, 各場合は O(1) で求められるので, 十分高速に答えを得られます。
const int MAX = 100100; ll dp[MAX]; ll sum[MAX]; ll ten[15]; int main() { cin.tie(0); ios::sync_with_stdio(false); ten[0] = 1; for (int i = 1; i < 15; i++) ten[i] = ten[i - 1] * 10; int A, B, P; while (cin >> A >> B >> P) { if (A == 0 && B == 0 && P == 0) break; memset(dp, 0, sizeof(dp)); memset(sum, 0, sizeof(sum)); for (int i = B; i >= A; i--) { dp[i - A] = 1; for (int j = 1; j < 6; j++) { ll mini = i*ten[j]; if (mini > B) continue; ll maxi = 0; while (mini >= ten[maxi]) maxi++; maxi = ten[maxi]; maxi = min<ll>(maxi, B + 1); dp[i - A] += sum[mini-A] - sum[maxi-A]; } for (int k = 9; k >= 0; k--) { if (i < ten[k] || (i / ten[k]) % 10 == 9) continue; ll mini = (i / ten[k] + 1) * ten[k]; ll maxi = (i / ten[k + 1] + 1)*ten[k + 1]; if (mini > B) continue; if (maxi > B) maxi = B + 1; //cout << i << " " << k << " " << mini << " " << maxi << endl; dp[i - A] += sum[mini-A] - sum[maxi-A]; } dp[i - A] = (dp[i - A] % P + P) % P; sum[i - A] = (sum[i - A + 1] + dp[i-A]) % P; //cout << i << " " << dp[i - A] << endl; } cout << sum[0] << endl; } return 0; }