AOJ 2326 Number Sorting

問題

全ての要素がA以上B以下の整数であるような集合のうち、
要素を小さい順に並べた列と、要素を辞書順に並べた列が一致するものの個数を、
mod Pで求めよ。

制約条件

A, B, P ≦10^9
B - A ≦ 100000

方針

ある数xを最後に使ったとき、次に使える要素を考える。

例えば、x = 135だとしたら、
135から999は、この集合の末尾に加えられる。
1350から、9999もこの集合の末尾に加えられる。
13500から、99999も……

となることがわかる。
したがって、配るDPができて、区間に効率的にたしこむことが出来れば効率的に
場合の数を求めることができる。

それには累積和を使えばいい。
135〜999に1を足すときは、dp[135]に1を足して、dp[1000]から1を引く、のような感じで。

ソースコード

ll a, b, p;
ll dp[110000];

int main()
{
	while(cin >> a >> b >> p, p){
		memset(dp, 0, sizeof(dp));
		
		dp[0] = 1;
		
		ll ans = 0;
		for(ll i = a; i <= b; i++){
			if(i > a) dp[i - a] = (dp[i - a] + dp[i - a - 1]) % p;
			ans = (ans + dp[i - a]) % p;
			
			for(ll j = i; j <= b; j *= 10){
				ll ten = 1;
				while(ten <= j) ten *= 10;
				
				ll x = max(i - a + 1ll, j - a), y = min(b - a + 1, ten - a);
				
				dp[x] = (dp[x] + dp[i - a]) % p;
				dp[y] = (dp[y] + p - dp[i - a]) % p;
			}
		}
		cout << ans << endl;
	}
	return 0;
}