# CodeForces 54C-First Digit Law（数位，概率dp）

dp[i][j]取前i个数，有j个是首位为1的数的概率

```#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod =  1000000007;
ll sum[20],a[20];
double dp[1010][1010],p[1010];
int bit[20],n,k;
void init(){
sum[0]=1;
for(int i=1;i<=20;++i)
sum[i]=sum[i-1]*10;
}
ll countsum(int l){
ll total=0;
for(int i=0;i<=l;++i)
total+=sum[i];
}
//统计首位为1数的数量
ll countone(ll x){
if(x==0)return 0;
init();
int len=0;
while(x){
bit[++len]=x%10;
x/=10;
}
if(bit[len]>1){
return countsum(len-1);
}
else{
ll tmp=countsum(len-2);
a[0]=0;
for(int i=1;i<=len-1;++i)
a[i]=a[i-1]+bit[i]*sum[i-1];
tmp+=a[len-1]+1;
return tmp;
}
}
int main()
{
ll l,r;
while(~scanf("%d",&n)){
for(int i=1;i<=n;++i){
scanf("%I64d%I64d",&l,&r);
ll tmp=countone(r)-countone(l-1);
//cout<<tmp<<endl;
p[i]=1.0*tmp/(r-l+1);
//cout<<p[i]<<endl;
}
dp[1][1]=p[1];
dp[1][0]=1.0-p[1];
for(int i=2;i<=n;++i)
for(int j=0;j<=i;++j){
dp[i][j]+=dp[i-1][j]*(1.0-p[i]);
if(j>0)
dp[i][j]+=dp[i-1][j-1]*p[i];
}
scanf("%d",&k);
double ans=0.0;
for(int j=0;j<=n;++j)
if(j>=(1.0*n*k/100))
ans+=dp[n][j];
printf("%.15lf\n",ans);
}
return 0;
}```

## CodeForces 540D Bad Luck Island 概率dp

CodeForces 540D 应该是简单概率dp,由于写得少显得十分蠢萌 求期望逆推,求概率正推,大概是这么个意思,贴一发留恋 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define db double const int maxn=108; db dp[maxn][maxn][maxn]; int main() { int i,j,n,m,k,p; whi

## Codeforces 148D Bag of mice (概率dp)

D. Bag of mice time limit per test:2 seconds memory limit per test:256 megabytes The dragon and the princess are arguing about what to do on the New Year's Eve. The dragon suggests flying to the mountains to watch fairies dancing in the moonlight, wh

## Codeforces 518D Ilya and Escalator (概率dp)

Ilya and Escalator time limit per test: 2 seconds memory limit per test: 256 megabytes Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor. Let's assume that

## Codeforces 28C [概率DP]

/* 大连热身D题 题意: 有n个人,m个浴室每个浴室有ai个喷头,每个人等概率得选择一个浴室. 每个浴室的人都在喷头前边排队,而且每个浴室内保证大家都尽可能均匀得在喷头后边排队. 求所有浴室中最长队伍的期望. 思路: 概率dp dp[i][j][k]代表前i个浴室有j个人最长队伍是k的概率. 枚举第i个浴室的人数.然后转移的时候其实是一个二项分布. */ #include<bits/stdc++.h> using namespace std; int jilu[55]; double dp[

## POJ1644:To Bet or Not To Bet(概率DP)

Description Alexander Charles McMillan loves to gamble, and during his last trip to the casino he ran across a new game. It is played on a linear sequence of squares as shown below. A chip is initially placed on the Start square. The player then trie