1 条题解
-
1
#include<bits/stdc++.h> using namespace std; int read() { char c; int w=1; while((c=getchar())>'9'||c<'0')if(c=='-')w=-1; int ans=c-'0'; while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0'; return ans*w; } long long gcd(long long a,long long b)//欧几里得算法 { return b==0?a:gcd(b,a%b); } struct node { long long a,b; void huajian()//让该分数成为既约分数 { long long w=gcd(a,b); a=a/w; b/=w; } node operator /(const long long y)const//一个分数除以一个整数 { node t = *this; t.b *= y,t.huajian(); return t; } node operator +(node y)const//一个分数加上另外一个分数 { if(a==0) { y.huajian(); return y; } node o=*this; if(y.a==0) { o.huajian(); return o; } long long p=gcd(o.b,y.b); o.a*=(y.b/p);o.a+=y.a*(o.b/p);o.b*=(y.b/p); o.huajian(); return o; } }f[1005][1005];//其实只要开50就够了! int n,m; int c[1005][1005]; int main(){ n=read(); m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { char w; while((w=getchar())!='*'&&w!='.'); if(w=='*')c[i][j]=1; } } f[0][1].a=1;//初始化 f[0][1].b=1; for(int i=1;i<=n+1;i++) { for(int j=1;j<=n+1;j++) { f[i][j].b=1;//注意要吧所有分数初始化一下,不然除以0化简时会RE } } for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { if(c[i][j]) { node p=f[i-1][j];//有钉子的时候 p=p/2; f[i][j]=f[i][j]+p; f[i][j+1]=f[i][j+1]+p; } else { f[i+1][j+1]=f[i+1][j+1]+f[i-1][j];//没有钉子的时候 } } } for(int i=1;i<=n;i++) for(int j=1;j<=i+1;j++) { f[i][j].huajian();//记得要化简哟!!! } f[n][m+1].huajian(); cout<<f[n][m+1].a<<"/"<<f[n][m+1].b<<endl;//cout大发好 return 0; }
- 1
信息
- ID
- 4672
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者