Advertisement
Guest User

Untitled

a guest
Nov 23rd, 2014
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.38 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/stack:16777216")
  3. #include <string>
  4. #include <vector>
  5. #include <map>
  6. #include <list>
  7. #include <iterator>
  8. #include <set>
  9. #include <queue>
  10. #include <iostream>
  11. #include <sstream>
  12. #include <stack>
  13. #include <deque>
  14. #include <cmath>
  15. #include <memory.h>
  16. #include <cstdlib>
  17. #include <cstdio>
  18. #include <cctype>
  19. #include <algorithm>
  20. #include <utility>
  21. #include <time.h>
  22. using namespace std;
  23.  
  24. #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
  25. #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
  26. #define REP(i, N) FOR(i, 0, N)
  27. #define RREP(i, N) RFOR(i, N, 0)
  28. #define FILL(A,value) memset(A,value,sizeof(A))
  29.  
  30. #define ALL(V) V.begin(), V.end()
  31. #define SZ(V) (int)V.size()
  32. #define PB push_back
  33. #define MP make_pair
  34. #define Pi 3.14159265358979
  35.  
  36. typedef long long Int;
  37. typedef unsigned long long UINT;
  38. typedef vector <int> VI;
  39. typedef pair <int, int> PII;
  40.  
  41. const int INF = 1000000000;
  42. const int MAX = 100007;
  43. const int MAX2 = 12;
  44. const int BASE = 1000000000;
  45. const int CNT = 317;
  46.  
  47. #define MOD 1000000009
  48.  
  49. int T;
  50. string A[3];
  51. char S[MAX];
  52. int C[28][28][28][3][3];
  53. int R[MAX][2][2];
  54.  
  55. int main()
  56. {
  57. freopen("in.txt", "r", stdin);
  58.  
  59. FOR (i,0,27)
  60. FOR (j,0,27)
  61. FOR (k,0,27)
  62. {
  63. int a = (i < j ? 0 : (i == j ? 1 : 2));
  64. int b = (j < k ? 0 : (j == k ? 1 : 2));
  65. FOR (mask,0,8)
  66. {
  67. int ii = i, jj = j, kk = k;
  68. if ((mask & 1) != 0)
  69. {
  70. if (i == 0)
  71. continue;
  72. ii = 27;
  73. }
  74. if ((mask & 2) != 0)
  75. {
  76. if (j == 0)
  77. continue;
  78. jj = 27;
  79. }
  80. if ((mask & 4) != 0)
  81. {
  82. if (k == 0)
  83. continue;
  84. kk = 27;
  85. }
  86.  
  87. C[ii][jj][kk][a][b] ++;
  88. }
  89. }
  90.  
  91. cout << int('?'+1) << endl;
  92. cin >> T;
  93. FOR (test,0,T)
  94. {
  95. FOR (i,0,3)
  96. {
  97. scanf("%s", S);
  98. int len = strlen(S);
  99. A[i] = "";
  100. FOR (j,0,len)
  101. A[i] += S[j];
  102. cout << A[i] << endl;
  103. }
  104. int len = 0;
  105. FOR (i,0,3)
  106. len = max(len, SZ(A[i]));
  107. FOR (i,0,3)
  108. FOR (j,0,SZ(A[i]))
  109. ++ A[i][j];
  110. while (SZ(A[0]) < len)
  111. A[0] += 'a';
  112. while (SZ(A[1]) < len)
  113. A[1] += 'a';
  114. while (SZ(A[2]) < len)
  115. A[2] += 'a';
  116. int n = SZ(A[0]);
  117. FOR (i,0,n+1)
  118. FOR (a,0,2)
  119. FOR (b,0,2)
  120. R[i][a][b] = 0;
  121. FOR (i,0,3)
  122. cout << A[i] << endl;
  123. R[0][1][1] = 1;
  124. FOR (i,0,n)
  125. FOR (a,0,2)
  126. FOR (b,0,2)
  127. {
  128. Int cur = R[i][a][b];
  129. if (cur == 0)
  130. continue;
  131. int ii = (A[0][i] == 64 ? 27 : A[0][i] - 'a');
  132. int jj = (A[1][i] == 64 ? 27 : A[1][i] - 'a');
  133. int kk = (A[2][i] == 64 ? 27 : A[2][i] - 'a');
  134. FOR (aa,0,3)
  135. FOR (bb,0,3)
  136. {
  137. if (a == 1 && aa == 2)
  138. continue;
  139. if (b == 1 && bb == 2)
  140. continue;
  141. int aaa = a;
  142. int bbb = a;
  143. if (aa == 0)
  144. aaa = 0;
  145. if (bb == 0)
  146. bbb = 0;
  147. R[i+1][aaa][bbb] += cur * C[ii][jj][kk][aa][bb] % MOD;
  148. //cout << A[0][i] << ' ' << ii << ' ' << jj << ' ' << kk << ' ' << aa << ' ' << bb << ' ' << C[ii][jj][kk][aa][bb] << endl;
  149. if (R[i+1][aaa][bbb] >= MOD)
  150. R[i+1][aaa][bbb] -= MOD;
  151. }
  152.  
  153. }
  154. printf("%d\n", R[n][0][0]);
  155.  
  156.  
  157. }
  158.  
  159.  
  160. return 0;
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement