Advertisement
Guest User

Untitled

a guest
Feb 1st, 2015
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.11 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <vector>
  5. #include <memory.h>
  6. #include <cstdlib>
  7. #include <ctime>
  8.  
  9. #define forn(i, n) for (int i = 0; i < (int) n; ++i)
  10.  
  11. typedef long long ll;
  12.  
  13. using namespace std;
  14.  
  15. const int MOD = 1e9 + 7;
  16. const int A = ('z' - 'a' + 1) + 1;
  17.  
  18. void add(int& x, int y) {
  19. ((x += y) >= MOD) && (x -= MOD);
  20. }
  21.  
  22. int mul(int x, int y) {
  23. return x * 1ll * y % MOD;
  24. }
  25.  
  26. int len = 0;
  27. char S[60][30];
  28. int s[60][30];
  29. int n;
  30.  
  31. int dp[55][55][22][30];
  32.  
  33. int sum_dp[55][55][22][30];
  34. bool was_sum[55][55][22];
  35.  
  36. int calc(int l, int r, int pos, int c);
  37.  
  38. void calc_sum(int l, int r, int pos) {
  39. if (was_sum[l][r][pos]) {
  40. return;
  41. }
  42. was_sum[l][r][pos] = true;
  43.  
  44. int res = 0;
  45. sum_dp[l][r][pos][0] = 0;
  46. forn(c, A) {
  47. add(res, calc(l, r, pos, c));
  48. sum_dp[l][r][pos][c + 1] = res;
  49. // add(sum_dp[l][r][pos][c + 1], sum_dp[l][r][pos][c]);
  50. }
  51. }
  52.  
  53. int calc(int l, int r, int pos, int c) {
  54. // printf("%d %d %d %d\n", l, r, pos, c);
  55.  
  56. if (l > r) {
  57. return 1;
  58. }
  59.  
  60. int& res = dp[l][r][pos][c];
  61.  
  62. if (res != -1) {
  63. return res;
  64. }
  65.  
  66. res = 0;
  67. for (int R = l; R <= r; ++R) {
  68. if (c == A - 1 && s[R][pos] != c) {
  69. break;
  70. }
  71.  
  72. if (s[R][pos] != A && s[R][pos] != c) {
  73. break;
  74. }
  75.  
  76. if (pos == len - 1 && R > l) {
  77. break;
  78. }
  79.  
  80. int cur1 = 0;
  81. if (pos < len - 1) {
  82. calc_sum(l, R, pos + 1);
  83. add(cur1, sum_dp[l][R][pos + 1][A]);
  84.  
  85. // for (int nc = 0; nc < A; ++nc) {
  86. // add(cur1, calc(l, R, pos + 1, nc));
  87. // }
  88. } else {
  89. cur1 = 1;
  90. }
  91.  
  92. int cur2 = 0;
  93. if (R == r) {
  94. cur2 = 1;
  95. } else {
  96. calc_sum(R + 1, r, pos);
  97. add(cur2, sum_dp[R + 1][r][pos][A]);
  98. add(cur2, -sum_dp[R + 1][r][pos][c + 1] + MOD);
  99.  
  100. // for (int nc = c + 1; nc < A; ++nc) {
  101. // add(cur2, calc(R + 1, r, pos, nc));
  102. // }
  103. }
  104.  
  105. add(res, mul(cur1, cur2));
  106. }
  107.  
  108. return res;
  109. }
  110.  
  111. int main()
  112. {
  113. // #define vlad
  114. #ifdef DEBUG
  115. freopen("input.txt", "rt", stdin);
  116. // freopen("output.txt", "w", stdout);
  117. #endif
  118.  
  119.  
  120. scanf("%d\n", &n);
  121. forn(i, n) {
  122. gets(S[i]);
  123.  
  124. int cur = strlen(S[i]);
  125. len = max(len, cur);
  126. }
  127.  
  128. /*
  129. len = 20;
  130. n = 50;
  131. forn(i, n) {
  132. forn(j, len) {
  133. s[i][j] = A;//rand() % (A + 1);
  134. }
  135.  
  136. } */
  137.  
  138. forn(i, n) {
  139. forn(j, strlen(S[i])) {
  140. if (S[i][j] == '?') {
  141. s[i][j] = A;
  142. } else {
  143. s[i][j] = S[i][j] - 'a';
  144. }
  145. }
  146.  
  147. for (int j = strlen(S[i]); j < len; ++j) {
  148. s[i][j] = A - 1;
  149. }
  150. }
  151.  
  152. /*
  153. printf("len = %d, n = %d\n", len, n);
  154. forn(i, n) {
  155. forn(j, len) {
  156. printf("%3d ", s[i][j]);
  157. }
  158. puts("");
  159. }
  160. puts("");
  161. printf("A = %d\n", A);
  162. */
  163.  
  164. memset (dp, -1, sizeof dp);
  165.  
  166. // printf("%d\n", s[0][0]);
  167. // printf("calc = %d\n", calc(0, 1, 0, 1));
  168.  
  169. // return 0;
  170. int res = 0;
  171. forn(c, A - 1) {
  172. add(res, calc(0, n - 1, 0, c));
  173. }
  174.  
  175. printf("%d\n", res);
  176. // printf("%.10f\n", (double) clock() / CLOCKS_PER_SEC);
  177. return 0;
  178. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement