Bình luận

• 

  TheBloxdPlayer • 9:33 p.m. 17 Tháng 3, 2025 •

  Code

  #include <bits/stdc++.h>
  
  using namespace std;
  typedef long long ll;
  const int maxN = 505;
  const ll MOD = 1e9+7;
  
  int N;
  char S[maxN];
  ll fac[maxN], inv[maxN], dp[maxN][maxN];
  
  ll fastpow(ll x, ll b){
      ll res = 1;
      while(b){
          if(b&1) res = (res * x) % MOD;
          x = (x * x) % MOD;
          b >>= 1;
      }
      return res;
  }
  
  ll choose(int n, int k){
      if(k < 0 || n < k)  return 0;
      return fac[n] * inv[k] % MOD * inv[n-k] % MOD;
  }
  
  void init(){
      fac[0] = inv[0] = 1;
      for(int i = 1; i < maxN; i++){
          fac[i] = (fac[i-1] * i) % MOD;
          inv[i] = fastpow(fac[i], MOD-2);
      }
  
      for(int i = 0; i < maxN; i++)
          for(int j = i; j < maxN; j++)
              dp[i][j] = -1;
  }
  
  ll solve(int l, int r){
      if((r-l+1)&1)       return 0;
      if(l > r)           return 1;
      if(dp[l][r] != -1)  return dp[l][r];
  
      ll cnt = 0;
      for(int m = l+1; m <= r; m++){
          if(S[l] == S[m]){
              ll subcases = solve(l+1, m-1) * solve(m+1, r) % MOD;
              ll aftercombine = subcases * choose((r-l+1)/2, (m-l+1)/2) % MOD;
              cnt = (cnt + aftercombine) % MOD;
          }
      }
  
      return dp[l][r] = cnt;
  }
  
  int main(){
      scanf(" %s", S);
      N = (int) strlen(S);
      init();
      printf("%lld\n", N&1 ? 0 : solve(0, N-1));
  } //  đã AC
  

  1

  Phản hồi Chia sẻ
• 

  vanphukhang_0604 • 8:29 p.m. 14 Tháng 8, 2023 • ← chỉnh sửa 2 →

  CSES - Empty String | Xâu Rỗng

  Cho một xâu gồm \(n\) kí tự từ a đến z.

  Mỗi lượt, bạn có thể xoá một cặp kí tự liền kề giống nhau bất kì. Mục tiêu của bạn là tạo một xâu trống bằng cách xoá tất cả các kí tự.

  Có bao nhiêu cách để đạt được mục tiêu trên?

  Input

  • Một dòng duy nhất chứa một xâu độ dài \(n \ (1 \leq n \leq 500)\).

  Output

  • In một số nguyên là số cách thực hiện sau khi chia lấy dư cho \(10^9 + 7\).

  Example

  Test 1

  Input

  aabccb

  Output

  3

  -2

  Phản hồi Chia sẻ