1 条题解

  • 0
    @ 2021-6-15 13:59:45

    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
    上传者