Submission #72476

#	Time	Username	Problem	Language	Result	Execution time	Memory
72476		(#118)	Dstorv (FXCUP3_dstorv)	C++17	38 / 100	28 ms	30048 KiB

dstorv

#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;

const int MOD = 1000000007;

int N, R, H, A, B;
int RR, RH;

char s[5002];
int upper[5002];

int dp[5002][5002]; // a개의 손을 없앴을 때 b개의 꽃이 죽음

char currentString[30][30];

int inv(int x){
  int v = 1, w = x, z = MOD - 2;

  while(z > 0){
    if(z & 1) v = 1LL * v * w % MOD;
    w = 1LL * w * w % MOD;

    z >>= 1;
  }

  return v;
}

int dfs(int d, int rc, int hc, int ratio){
  // first RH
  int x = 0;

  for(int i = 1; i < N - d; i++){
    if(currentString[d][i] == 'R' && currentString[d][i + 1] == 'H'){
      x = i; break;
    }
  }

  if(x == 0){ // end
    return rc == A && hc == B ? ratio : 0;
  }

  for(int i = 1; i < x; i++) currentString[d + 1][i] = currentString[d][i];
  for(int i = x + 2; i <= N - d; i++) currentString[d + 1][i - 1] = currentString[d][i];

  int res = 0;

  currentString[d + 1][x] = 'R';
  res += dfs(d + 1, rc, hc - 1, 1LL * ratio * RR % MOD);

  currentString[d + 1][x] = 'H';
  res += dfs(d + 1, rc - 1, hc, 1LL * ratio * RH % MOD);

  if(res >= MOD) res -= MOD;

  return res;
}

int main(){
  scanf("%d%d%d", &N, &R, &H);
  scanf("%s", s + 1);
  scanf("%d%d", &A, &B);

  int hc = 0, rc = 0;

  for(int i = 1; i <= N; i++){
    if(s[i] == 'R') rc++;
    else upper[++hc] = rc;
  }

  // printf("rc : %d, hc : %d\n", rc, hc);

  if(A > rc || B > hc){ puts("0"); return 0; }

  int den = inv(R + H);

  RR = 1LL * H * den % MOD; // R이 살아남음
  RH = 1LL * R * den % MOD; // H가 살아남음

  if(N <= 15){ // subtask 1
    for(int i = 1; i <= N; i++) currentString[0][i] = s[i];

    printf("%d\n", dfs(0, rc, hc, 1));
  }
  else{
    if(B != 0) assert(false);

    int res = 1;

    for(int i = 1; i <= rc - A; i++) res = 1LL * res * RH % MOD;
    for(int i = 1; i <= hc; i++) res = 1LL * res * RR % MOD;

    // printf("%d\n", res);

    dp[0][0] = 1;

    for(int i = 1; i <= hc; i++){
      int s = 0;

      // printf("upper : %d\n", upper[i]);

      for(int j = 0; j < upper[i]; j++){
        s += dp[i - 1][j]; if(s >= MOD) s -= MOD;
        dp[i][j] = s;
      }
    }

    int cnt = dp[hc][rc - A];

    printf("%lld\n", 1LL * res * cnt % MOD);
  }
  return 0;
}

Compilation message (stderr)

dstorv.cpp: In function 'int main()':
dstorv.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &N, &R, &H);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
dstorv.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
dstorv.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A, &B);
   ~~~~~^~~~~~~~~~~~~~~~

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