#include <iostream> using namespace std; int main() { int N; string s[600]; cin>>N; for(int i=0; i<N; ++i) { cin>>s[i]; } for(int i=0; i<N; ++i) { for(int j=0; j<N; ++j) { string S; S = s[i] + s[j]; int R; R = S.size(); int L[1200],P[1200],l,p; l = p = R; for(int i=R-1; i>=0; --i) { if(S[i] == 'L') { l = i; } else { p = i; } L[i] = l; P[i] = p; } int const C = 1000000007; long long dp[1202][602]; for(int i=0; i<1202; ++i) for(int j=0; j<602; ++j) dp[i][j] = 0; for(int i=0; i<=R; ++i) dp[i][0] = 1; for(int i=R-1; i>=0; --i) { for(int j=0; j<601; ++j) { dp[i][j] = (dp[i][j] + dp[L[i]+1][j+1]) % C; if(j > 0) dp[i][j] = (dp[i][j] + dp[P[i]+1][j-1]) % C; //cout<<dp[i][j]<<" "<<i<<" "<<j<<endl; } } cout<<dp[0][0]-1<<" "; } cout<<endl; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | #include <iostream> using namespace std; int main() { int N; string s[600]; cin>>N; for(int i=0; i<N; ++i) { cin>>s[i]; } for(int i=0; i<N; ++i) { for(int j=0; j<N; ++j) { string S; S = s[i] + s[j]; int R; R = S.size(); int L[1200],P[1200],l,p; l = p = R; for(int i=R-1; i>=0; --i) { if(S[i] == 'L') { l = i; } else { p = i; } L[i] = l; P[i] = p; } int const C = 1000000007; long long dp[1202][602]; for(int i=0; i<1202; ++i) for(int j=0; j<602; ++j) dp[i][j] = 0; for(int i=0; i<=R; ++i) dp[i][0] = 1; for(int i=R-1; i>=0; --i) { for(int j=0; j<601; ++j) { dp[i][j] = (dp[i][j] + dp[L[i]+1][j+1]) % C; if(j > 0) dp[i][j] = (dp[i][j] + dp[P[i]+1][j-1]) % C; //cout<<dp[i][j]<<" "<<i<<" "<<j<<endl; } } cout<<dp[0][0]-1<<" "; } cout<<endl; } return 0; } |