Submission #72423

#	Time	Username	Problem	Language	Result	Execution time	Memory
72423		BOJ 8481 (#118)	Dstorv (FXCUP3_dstorv)	C++17	9 / 100	4 ms	668 KiB

dstorv

#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

char s[7777];
char st[7777];
int top, idx;
const long long P=1000000007LL;
long long N,r,h,A,B,nofr,nofh;
long long ans,ansans;
long long llpow(long long x, long long n){
    if(n==1) return x;
    long long h=llpow(x,n/2);
    if(n&1) return ((h*h)%P*x)%P;
    return (h*h)%P;
}
long long invrh;
void push(char c){
    st[++top]=c;
}

int main(){OJize();
    cin>>N>>r>>h>>s>>A>>B;
    invrh=llpow(r+h,P-2);
    ans=1LL;
    nofr=nofh=0;
    for(int i=0;i<N;i++){
        if(s[i]=='R') nofr++;
        else nofh++;
    }
    for(int i=0;i<nofr-A;i++){
        ans=((ans*r)%P*invrh)%P;
    }
    for(int i=0;i<nofh-B;i++){
        ans=((ans*h)%P*invrh)%P;
    }
    if(N<=15){
        if(nofr<A || nofh<B) cout<<0;
        else{
            ansans=0LL;
            for(int i=0;i<(1<<(N-A-B));i++){
                top=-1;
                idx=0;
                for(int j=0;j<N-A-B;j++){
                    while(idx <= N){
                        if(top > 0 && st[top]=='H' && st[top-1]=='R') break;
                        if(idx!=N) push(s[idx]);
                        idx++;
                    }
                    if(idx>N) break;
                    if(i&(1<<j)){
                        top--;
                    }
                    else{
                        top--;
                        st[top]='H';
                    }
                }
                for(;idx<N;idx++) push(s[idx]);
                if(top==A+B-1){
                    int k;
                    for(k=0;k<B;k++){
                        if(st[k]!='H') break;
                    }
                    if(k==B){
                        for(k=0;k<A;k++){
                            if(st[B+k]!='R') break;
                        }
                        if(k==A) ansans++;
                    }
                }
            }
            ans=(ans*ansans)%P;
            cout<<ans;
        }
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 29
• Subtask 3: 0 / 62