fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  4. #define pii pair<int , int>
  5. #define pli pair<ll , int>
  6. #define pll pair<ll,ll>
  7. #define pil pair<int,ll>
  8. #define MASK(i) (1ll << i)
  9. #define bit(mask , i) ((mask >> i) & 1)
  10. #define debug cout << "NOBUG" << endl;
  11. #define fi first
  12. #define se second
  13. #define i128 __int128
  14. #define ldb long double
  15. #define el "\n"
  16. #define pb push_back
  17. #define ALL(vec) vec.begin(),vec.end()
  18. #define SORT_AND_UNIQUE(vec) sort(ALL(vec)); vec.erase(unique(ALL(vec)) , vec.end())
  19. #define lb(vec , x) lower_bound(ALL(vec) , x)
  20.  
  21. using namespace std;
  22. const ll oo = 0x3f3f3f3f;
  23. const int mod = 1e9+7 , MOD = 102e6 + 100829;
  24.  
  25. void File(string NAME) {
  26.     freopen((NAME + ".inp").c_str() , "r" , stdin);
  27.     freopen((NAME + ".out").c_str() , "w" , stdout);
  28. }
  29. template <class X , class Y>
  30.     bool maximize(X  &x , Y y) {
  31.         if(x < y) {
  32.             x = y;
  33.             return true;
  34.         }
  35.         return false;
  36.     }
  37. template <class X , class Y>
  38.     bool minimize(X  &x , Y y) {
  39.         if(x > y) {
  40.             x = y;
  41.             return true;
  42.         }
  43.         return false;
  44.     }
  45. template <class X , class Y>
  46.     void add_mod(X &x , Y y , int mod) {
  47.         x += y;
  48.         if(x >= mod) x -= mod;
  49.         if(x < 0) x += mod;
  50.     }
  51.  
  52. const int N = 250+1;
  53. int n;
  54. string s;
  55. int f[N] , nxt[N];
  56. int g[N][2];
  57.  
  58.  
  59. int main()
  60. {
  61.     fast
  62.     //File("TASK");
  63.     cin >> s;
  64.     int n = s.size();
  65.     s = " "+s;
  66.  
  67.     f[0] = 1;
  68.  
  69.     int ans = 0;
  70.  
  71.     for(int i = 1 ; i <= n ; i++) {
  72.         bool c = (s[i] == 'F');
  73.  
  74.         for(int sum = 0; sum < i ; sum++) nxt[sum] = f[sum];
  75.  
  76.         for(int sum = 0 ; sum < i ; sum++) {
  77.             if(sum+(c?1:-1) < 0) continue;
  78.  
  79.             add_mod(nxt[sum+(c?1:-1)] , f[sum]-g[sum][c] , mod);
  80.             g[sum][c] = f[sum];
  81.         }
  82.  
  83.         for(int sum = 0; sum <= i ; sum++) {
  84.             f[sum] = nxt[sum];
  85.             //cout << f[sum] <<' ';
  86.         }
  87.         //cout << el;
  88.     }
  89.  
  90.     cout << (f[0]-1+mod)%mod << el;
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/yKjjRt
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!