Submission #72474

#	Time	Username	Problem	Language	Result	Execution time	Memory
72474		BOJ 8481 (#118)	Dstorv (FXCUP3_dstorv)	C++17	9 / 100	3 ms	844 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];
long long dp[5020][5020];
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;
    
    // Task 1
    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;
        }
        return 0;
    }
    
    // Task 2
    dp[0][0] = 1;
    int pnt = 0;
    int accumulatedf = 0;
    for(int i=1; i<=nofh; i++){
        ll ssum = 0;
        int maxf = 0;
        while(pnt<N && s[pnt] == 'R') pnt++, maxf++, accumulatedf++;
        if(pnt == N){A-= maxf; break;}
        pnt++;
        for(int j=accumulatedf; j>=maxf; j--){
            ssum+= dp[i-1][j-maxf];
            ssum%= P;
            dp[i][j] = ssum;
        }
        for(int j=maxf-1; j>0; j--) dp[i][j] = ssum;
    }
    
    /*
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++) cout<<dp[i][j]<<' ';
        cout<<'\n';
    }*/
    
    if(A<0) cout<<0;
    else{
        ans = (ans * dp[nofh][A]) % P;
        cout<<ans;
    }
}

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