1 条题解
-
0
C++ :
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int BASE=(int)(1e8); struct node { int num[1005],top; node(int x=0) {*this=x;} int& operator[] (int k) {return num[k];} inline node operator = (int x) { top=0; if(!x) num[++top]=0; else for(;x;num[++top]=x%BASE,x/=BASE); return *this; } inline void modify() { int i=1,x=0; for(;x || i<=top;i++) { if(i>top) num[i]=0; x+=num[i]; num[i]=x%BASE;x/=BASE; } top=max(top,i-1); for(;top>1 && !num[top];top--); } inline void print() {printf("%d",num[top]);PER(i,top-1,1) printf("%08d",num[i]);} }; inline node operator + (node a,node b) { node c; c.top=max(a.top,b.top); REP(i,1,c.top) { if(i>a.top) a[i]=0; if(i>b.top) b[i]=0; c[i]=a[i]+b[i]; } c.modify();return c; } inline node operator - (node a,node b) { node c;int x=0; c.top=max(a.top,b.top); REP(i,1,c.top) { if(i>a.top) a[i]=0; if(i>b.top) b[i]=0; a[i]-=x;x=0; if(a[i]<b[i]) x=1; c[i]=x*BASE+a[i]-b[i]; } c.modify();return c; } LL tmp[1005]; inline node operator * (node a,node b) { node c; c.top=a.top+b.top-1; REP(i,1,c.top) tmp[i]=0; REP(i,1,a.top) REP(j,1,b.top) tmp[i+j-1]+=1LL*a[i]*b[j]; LL g=0; for(int i=1;i<=c.top || g;i++) { if(i>c.top) tmp[i]=0; g+=tmp[i];c[i]=g%BASE;g/=BASE; c.top=max(c.top,i); } return c; } inline node operator / (node a,int b) { node c;c.top=1; LL x=0; PER(i,a.top,1) { x=x*BASE+a[i]; if(x<b) continue; c[i]=x/b;x%=b; c.top=max(c.top,i); } return c; } inline int operator % (node a,int b) { int c=0; PER(i,a.top,1) c=(1LL*c*BASE+a[i])%b; return c; } struct fnode { node x,y; fnode(int _x=0,int _y=1) { int d=__gcd(_x,_y);_x/=d;_y/=d;x=_x;y=_y; } fnode(node _x,node _y):x(_x),y(_y) {} inline void chk() { REP(i,2,100) while(x%i==0 && y%i==0) x=x/i,y=y/i; } inline void print() {x.print();putchar('/');y.print();} }; inline fnode operator + (fnode a,fnode b) { return fnode(a.x*b.y+a.y*b.x,a.y*b.y); } inline fnode operator - (fnode a,fnode b) { return fnode(a.x*b.y-a.y*b.x,a.y*b.y); } inline fnode operator * (fnode a,fnode b) { return fnode(a.x*b.x,a.y*b.y); } inline fnode operator / (fnode a,fnode b) { return fnode(a.x*b.y,a.y*b.x); } char s[1005]; int f[1005],g[1005]; fnode K[1005],C[1005]; int main() { int p,q; read(p);read(q); scanf("%s",s+1); int n=strlen(s+1); for(int i=2,j=0;i<=n;i++) { while(j && s[i]!=s[j+1]) j=f[j]; if(s[i]==s[j+1]) j++;f[i]=j; } REP(i,1,n) { g[i]=i; while(g[i] && s[i+1]==s[g[i]+1]) g[i]=f[g[i]]; if(s[i+1]!=s[g[i]+1]) g[i]++; } fnode H=fnode(p,q),T=fnode(q-p,q),I=fnode(1,1); K[0]=fnode(1,1);C[0]=fnode(0,1); REP(i,1,n) { fnode A=H,B=T; if(s[i]=='T') swap(A,B); K[i]=(K[i-1]-B*K[g[i-1]])/A;K[i].chk(); C[i]=(C[i-1]-B*C[g[i-1]]+I)/A;C[i].chk(); } fnode res=C[n]/K[n];res.print();putchar('\n'); return 0; }
- 1
信息
- ID
- 970
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者