解题思路

算法设计

采用动态规划方法解决钉子概率问题：

核心思想

• 每层钉子的概率分布仅与上一层相关
• 通过动态规划递推计算各层概率
• 使用分数形式避免浮点数精度问题

状态转移方程

实现步骤

1. 初始化：
   • 设置f[1][1] = 2ⁿ（n为总层数）
   • 使用long long类型存储中间结果
2. 动态规划：
   • 逐层计算概率分布
   • 根据钉子存在情况应用不同转移方程
3. 结果处理：
   • 计算f[n+1][m+1]/f[1][1]
   • 约分得到最简分数形式

关键优化

• 分数表示：避免浮点数精度问题
• 大数处理：使用long long类型
• 约分算法：通过GCD计算最简分数

复杂度分析

• 时间复杂度：O(n²)，n为钉子层数
• 空间复杂度：O(n²)，存储动态规划表

# include <iostream>
# include <cstdio>
# include <cstring>
# define LL long long

using namespace std;
LL gcd(LL a, LL b)
{
    return b==0?a:gcd(b, a%b);
}

int main()
{
    LL dp[53][53];
    bool map[53][53];
    int n, m;
    while(~scanf("%d%d",&n,&m))
    {
        getchar();
        dp[1][1] = (LL)1<<n;//不能写成1<<n。
        for(int i=1; i<=n; ++i)
        {
            int k=1;
            string s;
            getline(cin, s);
            for(int j=0; j<s.size(); ++j)
            {
                if(s[j]=='*')
                    map[i][k++] = true;
                else if(s[j] == '.')
                    map[i][k++] = false;
                if(k == i+1)
                    break;
            }
        }
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=i; ++j)
            {
                if(map[i][j])//如果有钉，分两半。
                {
                    dp[i+1][j] += (dp[i][j]>>1);
                    dp[i+1][j+1] += (dp[i][j]>>1);
                }
                else//如果没钉，直接掉下去。
                    dp[i+2][j+1] += dp[i][j];
            }
        LL g = gcd(dp[n+1][m+1], dp[1][1]);
        printf("%lld/%lld\n",dp[n+1][m+1]/g, dp[1][1]/g);
    }
    return 0;
}