Submission #72442

#	Time	Username	Problem	Language	Result	Execution time	Memory
72442		(#118)	Dstorv (FXCUP3_dstorv)	C++17	29 / 100	34 ms	30436 KiB

dstorv

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

const int MOD = 1000000007;

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

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

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 main(){
  int N, R, H; scanf("%d%d%d", &N, &R, &H);

  scanf("%s", s + 1);

  int A, B; 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; }
  if(B != 0) assert(false);

  int res = 1, den = inv(R + H);

  for(int i = 1; i <= rc - A; i++) res = 1LL * res * R % MOD;
  for(int i = 1; i <= hc; i++) res = 1LL * res * H % MOD;
  for(int i = 1; i <= rc - A + hc; i++) res = 1LL * res * den % 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:26:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int N, R, H; scanf("%d%d%d", &N, &R, &H);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~
dstorv.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
dstorv.cpp:30:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int A, B; scanf("%d%d", &A, &B);
             ~~~~~^~~~~~~~~~~~~~~~

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