fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. constexpr int N = 3000 + 5;
  8. constexpr int P = 1e9 + 7;
  9.  
  10. char s[N];
  11. int fl[N][N] = {0};
  12. int fr[N][N] = {0};
  13.  
  14. signed main()
  15. {
  16.     ios::sync_with_stdio(false);
  17.     cin.tie(NULL);
  18.     cout.tie(NULL);
  19.  
  20.     // freopen("input.txt", "r", stdin);
  21.  
  22.     int n;
  23.     cin >> n;
  24.  
  25.     cin >> s;
  26.  
  27.     fl[0][0] = 1;
  28.  
  29.     for (int i = 0; i < n; i++) {
  30.         for (int j = 0; j <= n; j++) {
  31.             if (s[i] == '>') {
  32.                 fl[i + 1][j] = (fl[i + 1][j] + (long long) fl[i][j] * j) % P;
  33.                 fl[i + 1][j + 1] = (fl[i + 1][j + 1] + (long long) fl[i][j] * (j + 1)) % P;
  34.             } else {
  35.                 fl[i + 1][j] = (fl[i + 1][j] + (long long) fl[i][j] * j) % P;
  36.                 if (j > 1) {
  37.                     fl[i + 1][j - 1] = (fl[i + 1][j - 1] + (long long) fl[i][j] * (j - 1)) % P;
  38.                 }
  39.             }
  40.         }
  41.     }
  42.  
  43.     fr[n][0] = 1;
  44.  
  45.     for (int i = n; i; i--) {
  46.         for (int j = 0; j <= n; j++) {
  47.             if (s[i - 1] == '<') {
  48.                 fr[i - 1][j] = (fr[i - 1][j] + (long long) fr[i][j] * j) % P;
  49.                 fr[i - 1][j + 1] = (fr[i - 1][j + 1] + (long long) fr[i][j] * (j + 1)) % P;
  50.             } else {
  51.                 fr[i - 1][j] = (fr[i - 1][j] + (long long) fr[i][j] * j) % P;
  52.                 if (j > 1) {
  53.                     fr[i - 1][j - 1] = (fr[i - 1][j - 1] + (long long) fr[i][j] * (j - 1)) % P;
  54.                 }
  55.             }
  56.         }
  57.     }
  58.  
  59.     for (int i = 0; i < n; i++) {
  60.         int res = 0;
  61.         for (int a = 0; a <= n; a++) {
  62.             res = (res + (long long) fl[i][a] * fr[i + 1][a] * 2) % P;
  63.             if (a)
  64.             res = (res + (long long) fl[i][a] * fr[i + 1][a - 1]) % P;
  65.             if (a < n)
  66.             res = (res + (long long) fl[i][a] * fr[i + 1][a + 1]) % P;
  67.         }
  68.  
  69.         cout << res << ' ';
  70.     }
  71.  
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pwWGEw
language:
C++14 (clang 8.0)
created:
16 hours 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!