Advertisement
Guest User

Untitled

a guest
Jan 31st, 2015
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.42 KB | None | 0 0
  1. #include<ctime>
  2. #include<stdio.h>
  3. #include<string>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<vector>
  7. #include<set>
  8. #include<map>
  9. #include<queue>
  10. #include<list>
  11. #include<memory.h>
  12. using namespace std;
  13.  
  14. typedef long long ll;
  15. typedef vector<int> vi;
  16. typedef long double ld;
  17. typedef pair<int, int> pii;
  18. typedef pair<ll, ll> pll;
  19.  
  20. const int inf = 1e9+7;
  21. const ld eps = 1e-16;
  22. int n;
  23. char a[55][22], len[55];
  24. int f[22][55][55][30];
  25. bool marked[22][55][55][30];
  26. int maxLen[55][55];
  27. int qc[22][55][55];
  28.  
  29. int rec(int c, int l, int r, char maxQ){
  30. if(r < l)
  31. return 1;
  32. if(c >= maxLen[l][r])
  33. return 0;
  34.  
  35. if(marked[c][l][r][maxQ])
  36. return f[c][l][r][maxQ];
  37. marked[c][l][r][maxQ] = true;
  38.  
  39. if(l == r){
  40. if(c > len[l]){
  41. return f[c][l][r][maxQ] = 0;
  42. }else{
  43. ll q = 1;
  44. for(int i = c; i < len[l]; i++){
  45. if(a[l][i] == '?'){
  46. q = (q * maxQ) % inf;
  47. maxQ = 26;
  48. }else if(a[l][i] - 'a' < maxQ){
  49. maxQ = 26;
  50. }
  51. }
  52. return f[c][l][r][maxQ] = q;
  53. }
  54. }
  55.  
  56. int res = 0;
  57. int minQ = -1;
  58.  
  59. for(int i = l; i <= r; i++){
  60. char w = qc[c][i][r];
  61. if(w == 1)
  62. continue;
  63.  
  64. if(w != '?' && w - 'a' <= minQ)
  65. continue;
  66.  
  67. if(a[i][c] != '?' && a[i][c] - 'a' > minQ){
  68. minQ = a[i][c] - 'a';
  69. }
  70.  
  71. if(w == '?'){
  72. for(int q = minQ + 1; q < maxQ; q++){
  73. res += ((ll)rec(c + 1, i, r, 26) * rec(c, l, i - 1, q)) % inf;
  74. if(res > inf)
  75. res -= inf;
  76. }
  77. }else if(w - 'a' < maxQ){
  78. res += ((ll)rec(c + 1, i, r, 26) * rec(c, l, i - 1, w - 'a')) % inf;
  79. if(res > inf)
  80. res -= inf;
  81. }
  82. }
  83.  
  84. return f[c][l][r][maxQ] = res;
  85. }
  86.  
  87. int main(){
  88. #ifdef _BSUIR2JUDGE_
  89. freopen("input.txt", "r", stdin);
  90. freopen("output.txt", "w", stdout);
  91. #else
  92. //freopen("sum.in", "r", stdin);
  93. //freopen("sum.out", "w", stdout);
  94. #endif
  95.  
  96. memset(a, 0, sizeof(a));
  97.  
  98. scanf("%d\n", &n);
  99. for(int i = 0; i < n; i++){
  100. scanf("%s\n", &a[i][0]);
  101. len[i] = strlen(a[i]);
  102. }
  103.  
  104. for(int i = 0; i < n; i++){
  105. int ml = 0;
  106.  
  107. for(int j = i; j < n; j++){
  108. ml = max(ml, (int)len[j]);
  109. maxLen[i][j] = ml;
  110. }
  111. }
  112.  
  113. for(int k = 0; k < 22; k++){
  114. for(int i = 0; i < n; i++){
  115. char w = '?';
  116.  
  117. for(int j = i; j < n; j++){
  118. if(w != 1){
  119. if(a[j][k] != '?' && w != '?' && a[j][k] != w){
  120. w = 1;
  121. }else if(a[j][k] != '?'){
  122. w = a[j][k];
  123. }
  124. }
  125.  
  126. qc[k][i][j] = w;
  127. }
  128. }
  129. }
  130.  
  131. cout << rec(0, 0, n - 1, 26);
  132.  
  133. return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement