Fshl0

Empty String

Jun 1st, 2021
868
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. const ll MOD = 1e9 + 7;
  7. const ll N = 500 + 9;
  8.  
  9. ll F[N], Inv[N], rangeDP[N][N];
  10. string A;
  11.  
  12. ll Flex (ll);
  13.  
  14. ll bp (ll a, ll b) {
  15.     if (b == 0)
  16.         return 1;
  17.     ll tmp = bp (a, b / 2);
  18.     if (b & 1)
  19.         return Flex (Flex (tmp * tmp) * a);
  20.     return Flex (tmp * tmp);
  21. }
  22.  
  23. ll C (ll n, ll m) {
  24.     if (m > n)
  25.         return 0;
  26.     return Flex (F[n] * Flex (Inv[m] * Inv[n - m]));
  27. }
  28.  
  29. ll Flex (ll x) {
  30.     return (((x % MOD) + MOD) % MOD);
  31. }
  32.  
  33. ll Go (ll l, ll r) {
  34.     if (r < l)
  35.         return 1;
  36.     if (r == l + 1)
  37.         return A[l] == A[r];
  38.     if (l == r)
  39.         return 0;
  40.     if ((r - l + 1) & 1)
  41.         return 0;
  42.     if (rangeDP[l][r] != -1)
  43.         return rangeDP[l][r];
  44.     ll ret = 0;
  45.     if (A[l] == A[r]) {
  46.         ret += Go (l + 1, r - 1);
  47.         ret %= MOD;
  48.     }
  49.     for (ll i = l + 1; i < r; i++) {
  50.         if (A[l] == A[i]) {
  51.             ret += Flex (Flex (Go (l + 1, i - 1) * Go (i + 1, r)) * C ((r - l + 1) / 2, (i - l + 1) / 2));
  52.             ret %= MOD;
  53.         }
  54.     }
  55.     return rangeDP[l][r] = ret;
  56. }
  57.  
  58. int main () {
  59.     string s;
  60.     cin >> s;
  61.     ll n = s.length();
  62.     A = '#' + s;
  63.     F[0] = 1;
  64.     for (ll i = 1; i < N; i++)
  65.         F[i] = Flex (F[i - 1] * i);
  66.     Inv[N - 1] = bp (F[N - 1], MOD - 2);
  67.     for (int i = N - 2; i >= 0; i--)
  68.         Inv[i] = Flex (Inv[i + 1] * (i + 1));
  69.     memset (rangeDP, -1, sizeof (rangeDP));
  70.     cout << Go (1, n) << "\n";
  71.     return 0;
  72. }
  73.  
RAW Paste Data