Submission #869560

#	Time	Username	Problem	Language	Result	Execution time	Memory
869560		coldEr66	Dstorv (FXCUP3_dstorv)	C++17	0 / 100	94 ms	196872 KiB

dstorv

#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

const int mod = 1e9 + 7;

int fpow(int base, int exp = mod - 2, int ans = 1) {
    while (exp) {
        if (exp & 1) ans = ans * base % mod;
        exp >>= 1, base = base * base % mod;
    }
    return ans;
}

void cal(deque<char> &str, vector<int> &dp, int num) {
    if (num == 0) {
        dp[0] = 1;
        return;
    }
    int n = SZ(str) - 2;
    vector DP(n + 2, vector<int>(n + 2));
    vector<int> numR(n + 2), id(n + 2);
    int cnt = 0;
    int idx = 0;

    for (int i = 1; i <= n; ++i) {
        if (str[i] == 'H') {
            numR[++idx] = cnt;
            id[idx] = i;
        }
        else ++cnt;
    }

    DP[num][1] = 1;
    for (int i = num; i <= idx; ++i) {
        for (int j = 1; j <= numR[i]; ++j) {
            DP[i][j] = (DP[i][j] + DP[i-1][j]) % mod;
            DP[i][j] = (DP[i][j] + DP[i][j-1]) % mod;
        }
    }
    for (int i = num; i <= idx; ++i) {
        dp[id[i]] = DP[i][numR[i]];
        debug(i, dp[id[i]]);
    }
}

void solve() {
    int n, r, h; cin >> n >> r >> h;
    int tmpr = r * fpow(r + h), tmph = h * fpow(r + h);
    r = tmpr, h = tmph;

    string s; cin >> s;
    int a, b; cin >> a >> b;
    deque<char> dq(ALL(s));

    while (SZ(dq) && dq.back() == 'R') {
        dq.pb();
        n--, a--;
    }
    while (SZ(dq) && dq.front() == 'H') {
        dq.pf();
        n--, b--;
    }

    if (!SZ(dq)) {
        if (a == 0 && b == 0) print(1);
        else print(0);
        return;
    }
    else {
        if (a < 0 || b < 0) return print(0), void();
        dq.ef('$'), dq.eb('$');

        vector<int> dpl(n + 2), dpr(n + 2);
        cal(dq, dpl, b);

        reverse(ALL(dq));
        int cntR = 0, cntH = 0;
        for (int i = 1; i <= n; ++i) {
            if (dq[i] == 'R') dq[i] = 'H', ++cntR;
            else dq[i] = 'R', ++cntH;
        }
        cal(dq, dpr, a);
        reverse(ALL(dpr));

        int ans = 0;
        for (int i = 0; i <= n; ++i) ans = (ans + dpl[i] * dpr[i+1] % mod) % mod;
        debug(ans);

        ans = ans * fpow(r, cntR - a) % mod;
        ans = ans * fpow(h, cntH - b) % mod;

        print(ans);
    }

}

signed main() {
    IOS();
    int t = 1; // cin >> t;
    for (int i=1;i<=t;++i) solve();
    return 0;
}

#else

#ifdef local 
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;

#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
// #define X first
// #define Y second

#ifdef local
#define IOS() void()
#define debug(...) \
    fprintf(stderr, "\e[1;93m"), \
    fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
template <typename T> void _do(T &&_t) {cerr << _t << '\n';}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#define print(...) \
    fprintf(stderr, "\e[1;96m"), \
    _P(__VA_ARGS__), \
    fprintf(stderr, "\e[0m")
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#define endl '\n'
#endif

template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}

template <typename T> void _P(T &&_x) {cout << _x << '\n';}
template <typename T, typename ...S> void _P(T &&_x, S &&..._t) {cout << _x << " "; _P(_t...);}

#endif

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