题意

• 一个竖直放置的三角形模板，钉着n(n+1)/2颗钉子，最底下有(n+1)个格子
• 从最顶上落下一个小球，小球碰到钉子落向两边的概率相等
• 求去除m个钉子后，落到最底下第m+1格的概率是多少，以a/b的形式输出

思路

• 概率不好处理，不妨认为小球每下落一层就分裂成两个，在有钉子的地方，一个去左边，一个去右边
• 因此，没有钉子的时候会下落两层，由(i,j)到(i+2,j+1)
• 综上写出状态转移方程
  • 
  • 

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int a[100][100];
int dp[100][100];

signed main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            char tp;
            cin >> tp;
            a[i][j]=(tp=='*');
        }
    }

    dp[1][1]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            if(a[i][j]){
                dp[i+1][j+1]+=dp[i][j];
                dp[i+1][j]+=dp[i][j];
            }else{
                dp[i+2][j+1]+=4*dp[i][j];
            }
        }
    }
    // for(int i=1;i<=n+1;i++){
    //     for(int j=1;j<=i;j++){
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    int sum=0;
    for(int i=1;i<=n+1;i++){
        sum+=dp[n+1][i];
    }
    int base=gcd(sum,dp[n+1][m+1]);
    if(base==0)
        cout << "0/1" << endl;
    else
        cout << dp[n+1][m+1]/base << '/' << sum/base << endl;
    return 0;
}