fork download
copy 
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. #define ZMAX 27
  8. #define NMAX 111111
  9. #define LMAX 11
  10.  
  11. set<int> processed;
  12. double T[ZMAX][ZMAX], tmp[ZMAX][ZMAX], R[ZMAX][ZMAX];
  13. char s[LMAX], target[NMAX][LMAX];
  14.  
  15. int main() {
  16. //	freopen("y.txt", "r", stdin);
  17. 	int Tests, i, j, k, p, N, K, L;
  18. 	double ans, cans;
  19. 	scanf("%d", &Tests);
  20. 	while (Tests--) {
  21. 		scanf("%d %d %s", &N, &K, s);
  22. 		for (i = 1; i < ZMAX; i++)
  23. 			for (j = 1; j < ZMAX; j++)
  24. 				scanf("%lf", &T[i][j]);
  25. 		for (i = 1; i <= N; i++)
  26. 			scanf("%s", &target[i][0]);
  27. 		// Raise T to the power K.
  28. 		memset(R, 0, sizeof(R));
  29. 		for (i = 1; i < ZMAX; i++)
  30. 			R[i][i] = 1.0;
  31. 		for (p = 30; p >= 0; p--) {
  32. 			memset(tmp, 0, sizeof(tmp));
  33. 			for (i = 1; i < ZMAX; i++)
  34. 				for (j = 1; j < ZMAX; j++) {
  35. 					for (k = 1; k < ZMAX; k++)
  36. 						tmp[i][j] += R[i][k] * R[k][j];
  37. 				}
  38. 			memcpy(R, tmp, sizeof(R));
  39. 			if (K & (1 << p)) {
  40. 				memset(tmp, 0, sizeof(tmp));
  41. 				for (i = 1; i < ZMAX; i++)
  42. 					for (j = 1; j < ZMAX; j++) {
  43. 						for (k = 1; k < ZMAX; k++)
  44. 							tmp[i][j] += R[i][k] * T[k][j];
  45. 					}
  46. 				memcpy(R, tmp, sizeof(R));
  47. 			}
  48. 		}
  49. 		L = strlen(s);
  50. 		processed.clear();
  51. 		for (ans = 0.0, i = 1; i <= N; i++) {
  52. 			if (strlen(&target[i][0]) != L) continue;
  53. 			for (cans = 1.0, k = j = 0; j < L; j++) {
  54. 				cans *= R[s[j] - 'a' + 1][target[i][j] - 'a' + 1];
  55. 				k = k * ZMAX + target[i][j] - 'a' + 1;
  56. 			}
  57. 			if (processed.find(k) == processed.end()) {
  58. 				processed.insert(k);
  59. 				ans += cans;
  60. 			}
  61. 		}
  62. 		printf("%.9lf\n", ans);
  63. 	}
  64. 	return 0;
  65. }
  66.  
Success #stdin #stdout 0s 4684KB
comments (?)
stdin
copy 
1
2 1
a
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0.5 0 0.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.1 0.9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
ab
b
stdout
copy 
1.000000000
https://ideone.com/ypAUKH
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!