tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 2326

Number Sorting. 辞書順は小数にするとそのままソートできて楽です。
後はBITでDPするだけなので何も言うことはない。

#include<stdio.h>
#include<algorithm>
using namespace std;
int mod;
pair<double,int> v[131072];
int bit[131072];
int sum(int a,int b){
	if(a==0){
		int ret=0;
		for(b;b>=0;b=(b&(b+1))-1)ret=(ret+bit[b])%mod;
		return ret;
	}return (sum(0,b)-sum(0,a-1)+mod)%mod;
}
void add(int a,int b){
	for(;a<131072;a|=a+1)bit[a]=(bit[a]+b)%mod;
}
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),c){
		mod=c;
		b++;
		for(int i=a;i<b;i++){
			double now=(double)i;
			int keta=-1;
			int t=i;
			while(t){
				now*=0.1;
				keta++;
				t/=10;
			}
			now+=keta*(1e-11);
			v[i-a]=make_pair(now,i-a);
		}
		std::sort(v,v+b-a);
		for(int i=0;i<131072;i++)bit[i]=0;
		for(int i=0;i<b-a;i++){
			add(v[i].second,sum(0,v[i].second)+1);
		}
		printf("%d\n",sum(0,131071));
	}
}