[NOI1999]钉子和小球

第1行为整数n（2 ≤ n ≤ 50）和m（0 ≤ m ≤ n）。以下n行依次为木板上从上至下n行钉子的信息，每行中‘*’表示钉子还在，‘.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。

仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概p_m。既约分数的定义：A/B是既约分数，当且仅当A、B为正整数且A和B没有大于1的公因子。

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 464K, 提交时间: 2023-05-14 20:53:38

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll f[60][60];
int main()
{
  int n,m;
  cin>>n>>m;
  ll q=(ll)1<<n;
  f[0][0]=q;
  for(int i=0;i<n;i++)
  {
      for(int j=0;j<=i;j++)
      {
        char t;
        cin>>t;
        if(t=='*')f[i+1][j]+=f[i][j]/2,f[i+1][j+1]+=f[i][j]/2;
        else if(t=='.')f[i+2][j+1]+=f[i][j];
      }
  }
 
  if(!f[n][m])cout<<"0/1"<<endl;
  else
  { 
    ll w=__gcd(f[n][m],q);
  cout<<f[n][m]/w<<'/'<<q/w<<endl;
    }
}

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2019-01-07 18:12:56

#include<iostream>
using namespace std;
long long n,m,f[55][55],tot;
char map[55][55];
int main() {
 int i,j,k;
 cin>>n>>m;tot=1ll<<n;
 for(i=1;i<=n;i++)for(j=1;j<=i;j++)cin>>map[i][j];
 f[1][1]=tot;
 for(i=1;i<=n;i++)
  for(j=1;j<=i;j++)
   if(map[i][j]=='*')
    f[i+1][j]+=f[i][j]/2,f[i+1][j+1]+=f[i][j]/2;
   else f[i+2][j+1]+=f[i][j];
 if(f[n+1][m+1]==0){cout<<0<<'/'<<1;return 0;}
 while(f[n+1][m+1]%2==0){f[n+1][m+1]/=2;tot/=2;}
 cout<<f[n+1][m+1]<<'/'<<tot;
 return 0;
}

详情