mayoko’s diary

プロコンとかいろいろ。

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;
}