繼之前的機率dp，這次博文同樣和機率相關，但不僅僅限于dp處理。
UVA - 10288 Coupons
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1229
大意：買彩票，圖案有n種，如果收集到所有的n種彩票就能得到大獎。問平均情況下需要買多少張彩票？
分析：推狀态 ⟶
假設現在已經有了i種彩票，那麼購買j的機率就是：
設 p=in，購買j次的機率就是 pj−1(1−p)
那麼期望
E=1p0(1−p)+2p1(1−p)+3p2(1−p)+⋯+kpk−1(1−p)pE=p1(1−p)+2p2(1−p)+⋯+kpk(1−p)(1−p)E=(1−p)+p(1−p)+p2(1−p)+⋯+pk−1(1−p)−kpk(1−p)=(1−p)(1+p+p2+⋯+pk−1−kpk)E=1−pk1−p−kpk=1−pk−kpk(1−p)1−p=11−p=nn−i
那麼結果就是
∑i=0n−1nn−i
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){
return b==0?a:gcd(b,a%b);
}
int main()
{
LL n;
while(cin>>n){
LL p1=n,p2=n,d;
for(int i=1;i<n;i++){
p1=p1*(n-i)+p2*n;
p2=p2*(n-i);
d=gcd(p1,p2);
p1/=d; p2/=d;
}
LL ans=p1/p2;
p1=p1-ans*p2;
d=gcd(p1,p2);
p1/=d; p2/=d;
if(p1==0){
printf("%lld\n",ans);
continue;
}
LL len1=log10(ans)+1;
for(int i=0;i<len1;i++) printf(" "); printf(" ");
printf("%lld\n",p1);
printf("%lld ",ans);
LL len2=log10(p2)+1;
for(int i=0;i<len2;i++) printf("-"); printf("\n");
for(int i=0;i<len1;i++) printf(" "); printf(" ");
printf("%lld\n",p2);
}
return 0;
} poj 3744 Scout YYF I
http://poj.org/problem?id=3744
大意：在一段路途中，給出N個地雷地點，一個人一次走1步或者2步，求解順利通過此路的機率。
分析：N很小，其數組元素ai很大，列出轉移式子，dp[i]=p×dp[i−1]+(1−p)×dp[i−2]
當然，我們沒有那麼大的空間用于dp數組， 他隻是假想存在的。
對于通過ai的機率就是
(dp[i]dp[i−1])=(p11−p0)ai−1(dp[1]dp[0])=(p11−p0)ai−1(10)
如果能夠順利通過，那麼地雷點絕對是分界點！
分段：
1——x1
x1+1——x2
x2+1——x3
……
且到達x1+1，x2+1的機率是1！
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[15];
struct matrix{
double m[2][2];
}A;
matrix I={
1,0,
0,1
};
matrix multi(matrix m1,matrix m2){
matrix ans;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ans.m[i][j]=0;
for(int k=0;k<2;k++){
ans.m[i][j]+=m1.m[i][k]*m2.m[k][j];
}
}
}
return ans;
}
matrix power(matrix m1,int p){
matrix ans=I;
while(p){
if(p&1) ans=multi(ans,m1);
m1=multi(m1,m1);
p>>=1;
}
return ans;
}
int main()
{
//freopen("cin.txt","r",stdin);
int n;
double p;
while(~scanf("%d%lf",&n,&p)){
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
A.m[0][0]=p; A.m[0][1]=1-p;
A.m[1][0]=1; A.m[1][1]=0;
matrix t=power(A,a[0]-1);
double ans=t.m[0][0];
ans=1-ans;
for(int i=1;i<n;i++){
t=power(A,a[i]-a[i-1]-1); //
double temp=t.m[0][0];
ans=ans*(1-temp);
}
printf("%.7lf\n",ans);
}
return 0;
} hdu 5245 Joyful
http://acm.hdu.edu.cn/showproblem.php?pid=5245
大意：在棋盤中選兩個點作為子矩陣的對角線的點，該範圍内對格子圖色，問K次後塗色格子的方格期望。
分析：每次選擇A和B點這一事件是互相獨立的，且一個點可以多次重選。可以反着想，求出K次不被選中的機率，最後1減去它，就是選中的機率。
假設5區域的位置是一個格子(i,j)，統計包含5的情況數:
當A在1時，B可以在5,6,8,9 (i-1)(j-1)(m-i+1)*(n-j+1);
A在2時，B可以在4,5,6,7,8,9 (i-1)1(m-i+1)*n;
3: (i-1)(n-j)(m-i+1)*j;
4: 1*(j-1)*(n-j+1)*m;
5: m*n
6: (n-j)*1*j*m;
7: (m-i)(j-1)*i(n-j+1);
8: (m-i)*1*i*n;
9: (m-i)*(n-j)*i*j;
最後一個格子被覆寫的機率就是：1−(1−si,jm2n2)k
關于pow函數：
C++提供以下幾種pow函數的重載形式：
double pow(double X,int Y);
float pow(float X,float Y);
float pow(float X,int Y);
long double pow(long double X,long double Y);
long double pow(long double X,int Y);
靠！ 當pow()的指數參數是浮點數時，運作效率很低。很容易逾時。
但Y是整數時，利用分治遞歸可以提高效率。
自己寫函數替代pow(double, double)：
#include <stdio.h>
#include <math.h>
#define LL long long
int main()
{
//freopen("cin.txt","r",stdin);
int t,ca=1;
LL n,m,K;
scanf("%d",&t);
while(t--){
scanf("%I64d%I64d%I64d",&m,&n,&K);
double ans=0;
for(LL i=1;i<=m;i++){
for(LL j=1;j<=n;j++){
double s=0.0;
s+=(i-1)*(j-1)*(m-i+1)*(n-j+1);
s+=(i-1)*1*(m-i+1)*n;
s+=(i-1)*(n-j)*(m-i+1)*j; //3
s+=1*(j-1)*(n-j+1)*m;
s+=m*n;
s+=(n-j)*1*j*m;
s+=(m-i)*(j-1)*i*(n-j+1);
s+=(m-i)*1*i*n;
s+=(m-i)*(n-j)*i*j;
s=s/m/m/n/n;
//s=pow((1.0-s),1.0*K);
double tt=1.0-s;
s=1;
for(int it=0;it<K;it++){
s=s*tt;
}
ans=ans+1-s;
}
}
LL res=ans+0.5;
printf("Case #%d: %I64d\n",ca++,res);
}
return 0;
} 或者用C++的pow函數重載： pow(double, int) //不能用C寫，否則無法順利重載
#include <stdio.h>
#include <math.h>
#define LL long long
int main()
{
//freopen("cin.txt","r",stdin);
int t,ca=1;
LL n,m;
int K;
scanf("%d",&t);
while(t--){
scanf("%I64d%I64d%d",&m,&n,&K);
double ans=0;
for(LL i=1;i<=m;i++){
for(LL j=1;j<=n;j++){
double s=0.0;
s+=(i-1)*(j-1)*(m-i+1)*(n-j+1);
s+=(i-1)*1*(m-i+1)*n;
s+=(i-1)*(n-j)*(m-i+1)*j; //3
s+=1*(j-1)*(n-j+1)*m;
s+=m*n;
s+=(n-j)*1*j*m;
s+=(m-i)*(j-1)*i*(n-j+1);
s+=(m-i)*1*i*n;
s+=(m-i)*(n-j)*i*j;
s=s/m/m/n/n;
s=pow((1.0-s),K);
/*double tt=1.0-s;
s=1;
for(int it=0;it<K;it++){
s=s*tt;
}*/
ans=ans+1-s;
}
}
LL res=ans+0.5;
printf("Case #%d: %I64d\n",ca++,res);
}
return 0;
} 效率對比：
acdream 1113 The Arrow
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+10;
double dp[N];
int main()
{
int t,n;
cin>>t;
while(t--){
scanf("%d",&n);
memset(dp,0,sizeof(dp));
for(int i=n-1;i>=0;i--){
int k=0;
double temp=0;
for(int j=1;j<=6;j++){
if(i+j>n) k++;
else temp+=dp[i+j]*1.0/6;
}
temp++;
dp[i]+=temp*6.0/(6-k);
}
printf("%.2lf\n",dp[0]);
}
return 0;
}