http://blog.csdn.net/just_sort/article/details/51500004
http://poj.org/problem?id=3744

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 1005
struct Matrix
{
    double m[2][2];

};
Matrix operator *(const Matrix &a,const Matrix &b)
{
    Matrix c;
         for(int i=0;i<2;i++)
           for(int j=0;j<2;j++)
           {
               c.m[i][j]=0;
                for(int k=0;k<2;k++)
                {
                    c.m[i][j]+=a.m[i][k]*b.m[k][j];
                }
           }
           return c;
}
Matrix matrix_pow(Matrix a,int w)
{
    Matrix base=a,res;
    memset(res.m,0,sizeof(res.m));
    for(int i=0;i<2;i++)
    {
        res.m[i][i]=1;
    }
    int n=w;
    while(n)
    {
        if(n&1) res=res*base;
        n>>=1;
        base=base*base;
    }
    return res;
}
int main()
{
        int boom[15],n;
        double p,res;
        while(scanf("%d%lf",&n,&p)!=EOF)
        {
            res=1.0;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&boom[i]);
            }
            sort(boom+1,boom+n+1);
            boom[0]=0;
            Matrix A={p,1-p,1.0,0.0};
            for(int i=1;i<=n;i++)
            {
                Matrix B=matrix_pow(A,boom[i]-boom[i-1]-1);
                res*=(1-B.m[0][0]);
            }
            printf("%.7f\n",res);
        }
}

http://poj.org/problem?id=2151
http://blog.csdn.net/libin56842/article/details/10046785
ACM比賽中仓洼，共M道題，T個(gè)隊(duì)，pij表示第i隊(duì)解出第j題的概率
問(wèn) 每隊(duì)至少解出一題且冠軍隊(duì)至少解出N道題的概率允跑。

所有人最少做一題辨绊、最多的至少做N題颇象。那么我們控制第一個(gè)不變靠娱。就是最少做一題蓝纲。改變后面的抄邀。最后將多余的減掉就可以了耘眨。那么他的答案就是：所有的人至少做一題—所有人至少做一題并且最多的做出不超過(guò)N-1題。為什么因?yàn)檫@兩個(gè)因子都滿足所有人至少做一題境肾。將這個(gè)公因子提出來(lái)剔难，后面相減的就是最多的至少是N題。

#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
#define maxn 1005
double dp[1002][32][32];//第i隊(duì)做j道題前已經(jīng)做出k道題的概率
double arr[1002][32];
double s[1002][32];
int main()
{
        int n,m,t;
        while(scanf("%d%d%d",&m,&t,&n)!=EOF,m)
        {
            for(int i=1;i<=t;i++)
            {
                for(int j=1;j<=m;j++)
                    scanf("%lf",&arr[i][j]);
            }
            memset(dp,0,sizeof(dp));
            memset(s,0,sizeof(s));
            for(int i=1;i<=t;i++)
            {
                dp[i][0][0]=1.0;
                for(int j=1;j<=m;j++)
                    dp[i][j][0]=dp[i][j-1][0]*(1-arr[i][j]);
                for(int j=1;j<=m;j++)
                {
                    for(int k=1;k<=j;k++)
                    {
                        dp[i][j][k]=dp[i][j-1][k-1]*arr[i][j]+dp[i][j-1][k]*(1-arr[i][j]);
                    }
                }
                s[i][0]=dp[i][m][0];
                for(int j=1;j<=m;j++)
                {
                    s[i][j]=s[i][j-1]+dp[i][m][j];
                }
            }
            double p1=1.0,p2=1.0;
            for(int i=1;i<=t;i++)
                p1*=(s[i][m]-s[i][0]);
            for(int i=1;i<=t;i++)
                p2*=(s[i][n-1]-s[i][0]);
            printf("%.3f\n",p1-p2);


        }
}