54 C First Digit Law

問題

n個の自然数が、それぞれ[ L[i], R[i] ]の区間から等しい確率で選ばれる。
n個のうちK%以上が、先頭の数字が1である確率を求めよ。

制約条件

n≦1000,
L[i],R[i]≦10^18

方針

区間[ L[i],R[i] ]に含まれる、先頭が1である数をdpにより求めればよい。

m以下の数で先頭が1であるような数の数は次のようなdpにより求められる。
dp[位置][先頭に1が出たか][mより小さいか]としてテーブルを更新していく。

doubleだと精度不足らしく落ちる。long doubleにしたら通った。

ソースコード

ll d[20][2][2]; //pos, one, smaller
long double calc(ll m){
	char s[20];
	sprintf(s,"%I64d",m);
	
	int n=strlen(s);
	memset(d,0,sizeof(d));
	d[0][0][0]=1;
	rep(i,n)rep(j,2)rep(k,2){
		rep(l,10){
			int none=j,nsm=k;
			if(j==0&&l==1)none=1;
			if(l<s[i]-'0')nsm=1;
			if(j==0&&l>1||!k&&l>s[i]-'0')continue;
			d[i+1][none][nsm]+=d[i][j][k];
		}
	}
	return d[n][1][0]+d[n][1][1];
}

long double dp[1001][1001];
void run()
{
	int n,k;
	vector<long double> v;
	cin>>n;
	
	rep(i,n){
		ll l,r; cin>>l>>r;
		v.pb((calc(r)-calc(l-1))/(r-l+1));
	}
	cin>>k;
	
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	rep(i,n)rep(j,i+1){
		dp[i+1][j+1]+=dp[i][j]*v[i];
		dp[i+1][j]+=dp[i][j]*(1-v[i]);
	}
	
	long double ans=0;
	for(int i=(int)(ceil(n*k/100.0-EPS));i<=n;i++)ans+=dp[n][i];
	cout<<setiosflags(ios::fixed)<<setprecision(20)<<ans<<endl;
}