fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6. #include <set>
  7. #include <map>
  8. #include <cmath>
  9. #include <cstring>
  10. #include <ctime>
  11. #include <unordered_map>
  12. #include <iomanip>
  13. #include <complex>
  14. #include <cassert>
  15. using namespace std;
  16.  
  17. #define fi first
  18. #define se second
  19. #define pb push_back
  20. #define all(v) (v).begin(),(v).end()
  21. #define deb(a) cerr<< #a << "= " << (a)<<"\n";
  22.  
  23. typedef long long ll;
  24. typedef unsigned long long ull;
  25. typedef unsigned int uint;
  26. typedef long double ld;
  27. typedef complex<double> base;
  28. typedef vector<int> vi;
  29. typedef pair<int,int> pii;
  30.  
  31. const int mod=1000000007;
  32. template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream; }
  33. ll fpow(ll x, ll p, ll m){ll r=1; for (;p;p>>=1){ if (p&1) r=r*x%m; x=x*x%m; } return r;}
  34. int gcd(int a, int b){ if (!b) return a; return gcd(b,a%b);}
  35. ll gcd(ll a, ll b){ if (!b) return a; return gcd(b,a%b);}
  36.  
  37. void add(int &x, int y){
  38. 	x=(1LL*x+y)%mod;
  39. }
  40.  
  41. int N,dp1[5010][5010],dp2[5010][5010],ans[5010]; char a[5010];
  42. string s;
  43.  
  44. int main(){
  45. 	ios::sync_with_stdio(0);
  46. 	cin.tie(0);
  47. 	cin >> s;
  48. 	N=s.length();
  49.  
  50. 	if (N==1){
  51. 		cout << 1 << "\n";
  52. 		return 0;
  53. 	}
  54. 	int i,j;
  55. 	for (i=1; i<=N; i++)
  56. 		a[i]=s[i-1];
  57.  
  58.  
  59. 	dp1[N+1][1]=1;
  60. 	for (i=N; i>0; i--){
  61. 		for (j=1; j<=i; j++){
  62. 			if (a[i]=='<'){
  63. 				add(dp1[i][j],1LL*j*dp1[i+1][j]%mod);
  64. 				add(dp1[i][j],1LL*(j-1)*dp1[i+1][j-1]%mod);
  65. 			}
  66. 			else{
  67. 				add(dp1[i][j],1LL*j*dp1[i+1][j+1]%mod);
  68. 				add(dp1[i][j],1LL*(j-1)*dp1[i+1][j]%mod);
  69. 			}
  70. 		}
  71. 	}
  72.  
  73.  
  74.  
  75. 	if (a[1]!='<') 
  76. 		dp2[1][1]=1;
  77. 	for (i=1; i<N; i++)
  78. 		for (j=1; j<=i; j++){
  79. 			if (a[i+1]=='<'){
  80. 				add(dp2[i+1][j],1LL*j*dp2[i][j]%mod);
  81. 				add(dp2[i+1][j-1],1LL*(j-1)*dp2[i][j]%mod);
  82. 			}
  83. 			else{
  84. 				add(dp2[i+1][j],1LL*j*dp2[i][j]%mod);
  85. 				add(dp2[i+1][j+1],1LL*(j+1)*dp2[i][j]%mod);
  86. 			}
  87. 		}
  88.  
  89.  
  90.  
  91. 	ans[1]=dp1[2][1];
  92. 	ans[N]=dp2[N-1][1];
  93.  
  94. 	for (i=2; i<N; i++){
  95. 		for (j=1; j<i; j++){
  96. 			ll v=1LL*dp2[i-1][j]*(dp1[i+1][j]+dp1[i+1][j+1])%mod;
  97. 			ans[i]=(1LL*ans[i]+v)%mod;
  98. 		}
  99. 	}
  100.  
  101. 	for (i=1; i<=N; i++)
  102. 		cout << ans[i] << " ";
  103. 	cout << "\n";
  104. 	return 0;
  105. }
  106.  
Success #stdin #stdout 0s 212160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/PVcA0N
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
6 years 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!