Codeforces Beta Round #50 First Digit Law(概率dp+数位dp)

题目

给你N(N<=1e3)个区间，第i个区间[Li,Ri](1<=Li<=Ri<=1e18)

依次在第i个区间里等概率地选择一个数，

如果选择的数是1开头的，则称为这次是好的选择

求好的选择在N次选择中至少占K%(0<=K<=100)的概率

题解

在数位dp这里还是有很多不足，回头需要再刷

如果能求出，对于第i个选择是好的选择的概率one，

则记dp[i][j]为前i个区间里好的选择占了j个的概率，dp[i][j]=dp[i-1][j]*one+dp[i-1][j-1]*none

最后满足j>=n*K%的dp[n][j]的概率和即为所求

one的求法需要用数位dp，前缀和cal(r)-cal(l-1)

dfs传三个参，其中pre=-1代表现在还在前导0阶段即没填数，pre=i代表最后一个填的是i

lim是正常的是否受上界影响，具体记忆化时，只有18个前缀会需要单独计算

用-1去搜1和-1的情况，用1去搜i的情况，就能保证开头一定是1了

对于之前还没填的情况，要么这位不填，要么这位填1

对于之前已经填过首位1的情况，这位填的不超过上界即可

判断什么时候需要记忆化，对于已经出现开头1来说，后续方案数只与位数有关，因此不受最高位限制即可

数位dp部分用for循环硬凑亦可，这里补数位dp的写法

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
typedef long long ll;
int n,k,len,mn;
ll l,r,a[20],sz[20];
double ans,dp[N][N],one,none;

//pre==-1代表没填 等价于前导0 
//保证了pre=-1只会搜出pre=1和pre=-1
//pre=1再往下搜才会搜出pre=i 所以底层情况都合法 
//满足lim==1的 只有数的18个前缀 
ll dfs(int pos,int pre,bool lim)
{
	if(pos==0)return 1;
	if(~sz[pos] && ~pre && !lim)return sz[pos];
	ll ret=0;
	int up=lim?a[pos]:9;
	if(pre==-1)ret+=dfs(pos-1,1,lim&&a[pos]==1)+dfs(pos-1,-1,0);
	else
	{ 
		for(int i=0;i<=up;++i)
			ret+=dfs(pos-1,i,lim&&(i==up));
	}
	return !lim?sz[pos]=ret:ret;//注意到方案数只受非lim限制不受前导0限制 
}

ll part(ll x)
{
	len=0;
	while(x)a[++len]=x%10,x/=10;
	memset(sz,-1,sizeof sz);
	return dfs(len,-1,1); 
}

int main()
{
	scanf("%d",&n);
	dp[0][0]=1;
	for(int i=1;i<=n;++i)
	{
		scanf("%lld%lld",&l,&r);
		one=(part(r)-part(l-1))*1.0/(r-l+1.0);
		none=1-one;
		dp[i][0]=dp[i-1][0]*none;
		for(int j=1;j<=i;++j)
		dp[i][j]=dp[i-1][j]*none+dp[i-1][j-1]*one; 
	}
	scanf("%d",&k);
	mn=(n*k+99)/100;
	for(int i=mn;i<=n;++i)
	ans+=dp[n][i];
	printf("%.10lf\n",ans);
	return 0;
}