ACM-概率题(其一)

说是DP，其实完全可以视为递推
Tribles

题意：
一开始有k个某种生物，这种生物只能活1天，死的时候有pi 的概率产生i只这种生物（也只能活一天），询问m天内所有生物都死亡的概率

分析:
一下子看k个比较复杂，而且貌似k个可以分为一个一个的k组，组和组之间并没有影响。
而显然的，假设前m天内一组死亡的概率是p，那么两组死亡的概率就是p²，k组死亡的概率就是p^k

所以我们只需先分析一只的情况就可以。

第一天有一只，最后所有麻雀假设在i天内全部都死掉了，那么第一只麻雀在第一天产生的麻雀就需要在i-1天内全死掉，然后子一代的子代就需要在i-2天内全部死掉，以此类推，第i天的子代在之后i-1天内全部死光就有如下公式，我们只需要把i从1搞到m就可以了。

(其中，以第n项为例，其意义就是第i天产生了n-1个子代，并且在i-1天内全部死亡的概率)

而这也正好和全概率公式是相互对应的(全概率公式，假如有若干个事件都可以到达事件B，那么事件B的总概率就是这所有事件A和B的条件概率之和)

下方放上全概率与条件概率的原理图

（这里用到了条件概率，计算方式与原理如下）

#include 

using namespace std;
const int N = 1e5+100;
double fastpow(int n,double a)
{
    double res=1.0;
    while(n)
    {
        if(n&1)
        {
            res=res*a;
        }
        n>>=1;
        a=a*a;
    }
    return res;
}
double p[N],dp[N];//dp[i]代表所有生物在i天内暴毙的概率
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t,cnt=0;
    for(cin>>t;t;t--)
    {
        cnt++;
        int n,k,m;
        cin>>n>>k>>m;
        for(int i=0;i<n;i++)
        {
            cin>>p[i];
        }
        dp[1]=p[0];
        for(int i=2;i<=m;i++)
        {
            dp[i]=0;
            for(int j=0;j<n;j++)
            {
                dp[i]+=p[j]*fastpow(j,dp[i-1]);
            }
        }
        cout<<"Case #"<<cnt<<": "<<fixed<<setprecision(7)<<fastpow(k,dp[m])<<'\n';
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

Joining with Friend

题意：两人会面，第一个人去的时间在[t1, t2]中，第二个人去的时间在[s1, s2]中，两人会面成功的话，到达会面地点的时间差不能大于w，求两人成功会面的概率。

思路：假设第一个人到达的时间为x，第二个人到达的时间为y，那么两人再符合题目要求的时间内会面则可有有如下不等式
|x-y|<=w。

以二维坐标系来划分，x轴找出[t1, t2]，y轴找出[s1, s2]，则可以表示出一个矩形，这个矩形的面积就是全部情况。

根据不等式
得到两条直线
y=x-w
y=x+w
那么这两条直线和矩形相交并且所夹的中间的这块区域就是要求的情况，但是这样需要算的东西有些太多了，不妨直接算出一大块面积减去一小块。

则用第一条直线切割的矩形上半部分面积减去第二条直线切割的矩形上半部分面积

概率显然就好求了。

#include 

using namespace std;

const int N = 50007;

int n, m, t;
double s1, s2, t1, t2, w;
int kcase;

double get_area(double b)
{
	if(t1 + b >= s2) return 0;
	if(t2 + b <= s1) return (t2 - t1) * (s2 - s1);
	if(t1 + b >= s1 && t2 + b <= s2) return (t2 - t1) * (s2 - t2 - b + s2 - t1 - b) * 0.5;
	if(t1 + b >= s1 && t2 + b > s2) return (s2 - b - t1) * (s2 - b - t1) * 0.5;
	if(t1 + b <= s1 && t2 + b >= s2) return (s2 - s1) * (s1 - b - t1 + s2 - b - t1) * 0.5;
	if(t1 + b < s1 && t2 + b < s2 && t2 + b > s1) return (t2 - t1) * (s2 - s1) - (t2 + b - s1) * (t2 + b - s1) * 0.5;
	return 0;
}

void solve()
{
	scanf("%lf%lf%lf%lf%lf", &t1, &t2, &s1, &s2, &w);
	printf("Case #%d: ", ++ kcase);
	double tot = (t2 - t1) * (s2 - s1);
	double up = get_area(-w) - get_area(w);
	printf("%.8f\n", up / tot);
}

int main()
{
	scanf("%d", &t);
	while(t -- ) {
		solve();
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

条件概率 Probability|Given

题意：已知n个人买东西的概率，现在知道这些人里有r个人是买了东西的，那么求每个人买东西的概率。

根据条件概率公式，假设已经有r-1个人买了东西，那么现在考虑的这个人买东西和不卖东西的概率都可以用条件概率的公式算出来。

又因为有n个人，每个人买和不卖就分为了两种情况，最后一共最多有2ⁿ种情况，对于这些情况，我们每次都把每个人相应的概率累计求和，然后再算一个总的概率和，最后每个人的概率就是:单个人在所有情况下的概率/总的概率

#include 

using namespace std;

const int N = 1e5+100;

double p[N],tot;
double sum[N];
int n,r;
void DFS(int cnt,int num,double p1)
{
    if(r-num>n-cnt||num>r)
    {
        return ;
    }
    if(cnt==n)
    {
         tot+=p1;
         for(int i=1;i<=n;i++)
         {
             if(vis[i])
             {
                 sum[i]+=p1;
             }
         }
         return ;
    }
    vis[cnt]=0;
    DFS(cnt+1,num,p1*(1-p[cnt]));
    vis[cnt]=1;
    DFS(cnt+1,num+1,p1*p[cnt]);
}

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n,r;
    while(1)
    {
        cin>>n>>r;
        for(int i=1;i<=n;i++)
        {
            cin>>p[i];
        }
        DFS(1,0,0.0);
        for(int i=1;i<=n;i++)
        {
            cout<<sum[i]/tot<<'\n';
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

E. Wish I Knew How to Sort（概率期望，概率论）

题意：给定一个01串，每次可以选择一对下标[i,j] (i!=j)，然后交换这两个下标对应的数，问你将整个串交换为有序的期望是多少。

思路：

抽象模型
首先假设我们有x个0，那么题目期望达到的最终状态就是前x个位置都是0，也就是要把前x个位置里的前的所有1都交换出去。

1.概率论基础：若干事件的期望是每个事件期望的和。
应用到这个题上就是：每个1被交换出去的期望相加。

再来每个1被交换出去的期望，发现一共有n*(n-1)/2个下标对可以选择，其中满足能把1交换出去的是cntcnt（cnt是当前遍历到的前x个位置中1的个数）个。所以成功选择的概率就是cnt * cnt/(n(n-1)/2)

2.伯努利事件与几何分布。

#include 
#include 
using namespace std;
#define int long long
#define endl '\n'
const int N = 2e6+100;
const int mod =998244353;
int fastpow(int n,int a)
{
    int res=1;
    a%=mod;
    while(n)
    {
        if(n&1)
        {
            res=res*a%mod;
        }
        a=a*a%mod;
        n>>=1;
    }
    return res%mod;
}
int a[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(!a[i])
                cnt++;
        }
        int x=0;
        int tot=n*(n-1)/2;
        tot%=mod;
        int ans=0;
        for(int i=1;i<=cnt;i++)
        {
            if(a[i])
            {
                x++;
                ans=(ans%mod+tot*fastpow(mod-2,x*x)%mod+mod)%mod;
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54