Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贴一个#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int N = 55; long long gcd(long long a, long long b) { if(a < b) { a = a^b; b = a^b; a= a^b; } long long tmp = 0; while((tmp = a % b) != 0) { a = b; b = tmp; } return b; } int main() { char triangle[N][N]; int n,m; cin>>n>>m; for(int i = 0; i < n; i++) { for(int j = 0; j <= i; j++) { cin>>triangle[i][j]; } } long long dp[N][N]; memset(dp,0,sizeof(dp)); dp[0][0] = (long long)1 << n; for(int i = 0; i < n; i++) { for(int j = 0; j <=i; j++) { if(triangle[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]; } } } long long num = gcd(dp[n][m],(long long)1<<n); cout<<dp[n][m]/num<<"/"<<((long long)1<<n)/num<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator