fork download
copy 
  1. public class MappingABC {
  2. 	final int MOD = 1000 * 1000 * 1000 + 7;
  3.  
  4. 	int[][] forbidden; // 'x' can be mapped to a letter 'y' only if forbidden[x][y] = 0
  5. 	int[] total = new int[4]; // total[x] = how many numbers have 'x' possible letters
  6. 	int[][] my_pow;
  7.  
  8. 	void computePow() {
  9. 		my_pow = new int[total.length][forbidden.length+1];
  10. 		for(int c = 0; c < total.length; ++c)
  11. 			for(int i = 0; i <= forbidden.length; ++i) {
  12. 				if(i == 0)
  13. 					my_pow[c][i] = 1;
  14. 				else
  15. 					my_pow[c][i] = (int) ((long) my_pow[c][i-1] * c % MOD);
  16. 			}
  17. 	}
  18.  
  19. 	int toAnswer() {
  20. 		int r = 1;
  21. 		for(int c = 0; c < total.length; ++c)
  22. 			r = (int) ((long) r * my_pow[c][total[c]] % MOD);
  23. 		return r;
  24. 	}
  25.  
  26. 	void clear() {
  27. 		for(int i = 0; i < forbidden.length; ++i)
  28. 			Arrays.fill(forbidden[i], 0);
  29. 		Arrays.fill(total, 0);
  30. 	}
  31.  
  32. 	int countLetters(int x) {
  33. 		int letters = 0;
  34. 		for(int i = 0; i < 3; ++i)
  35. 			if(forbidden[x][i] == 0)
  36. 				++letters;
  37. 		return letters;
  38. 	}
  39.  
  40. 	void forget(int x) { --total[countLetters(x)]; }
  41. 	void remind(int x) { ++total[countLetters(x)]; }
  42.  
  43. 	void add(int x, int y) { // 'x' can't be mapped to a letter 'y'
  44. 		forget(x);
  45. 		++forbidden[x][y];
  46. 		remind(x);
  47. 	}
  48. 	void sub(int x, int y) { // cancel add()
  49. 		forget(x);
  50. 		--forbidden[x][y];
  51. 		remind(x);
  52. 	}
  53.  
  54. 	public int countStrings(int[] t) {
  55. 		int n = t.length;
  56. 		int MAX_VAL = 0;
  57. 		for(int i = 0; i < n; ++i) {
  58. 			MAX_VAL = max(MAX_VAL, t[i]);
  59. 			--t[i];
  60. 		}
  61. 		boolean appears[] = new boolean[MAX_VAL];
  62. 		for(int i = 0; i < MAX_VAL; ++i)
  63. 			appears[i] = false;
  64. 		for(int x : t)
  65. 			appears[x] = true;
  66. 		forbidden = new int[MAX_VAL][3];
  67. 		computePow();
  68.  
  69. 		int answer = 0;
  70. 		final int A = 0, B = 1, C = 2;
  71. 		for(int rep = 0; rep < 2; ++rep) {
  72. 			boolean NO_C = rep == 1; // in the second run of the loop
  73. 			// we don't allow letters 'C' at the end
  74. 			for (int a0 = 0; a0 < n; ++a0) {
  75. 				clear();
  76. 				for(int i = 0; i < MAX_VAL; ++i)
  77. 					if(appears[i])
  78. 						++total[3]; // it can be mapped to any of 3 letters
  79. 				for (int i = 0; i < a0; ++i)
  80. 					add(t[i], A); // no 'A'
  81. 				add(t[a0], B); add(t[a0], C); // first 'A'
  82. 				if (NO_C)
  83. 					for (int i = a0 + 1; i < n; ++i)
  84. 						add(t[i], C); // no 'C'
  85. 				for (int b0 = a0 + 1; b0 < n; ++b0) {
  86. 					int memo = answer;
  87. 					if (NO_C)
  88. 						sub(t[b0], C); // cancel
  89. 					add(t[b0], A); add(t[b0], C); // first 'B'
  90. 					if (NO_C)
  91. 						answer = (answer - toAnswer() + MOD) % MOD;
  92. 					else
  93. 						answer = (answer + toAnswer()) % MOD;
  94. 					sub(t[b0], A); sub(t[b0], C); // cancel
  95. 					add(t[b0], B); // no 'B'
  96. 					// System.out.println(NO_C + " " + a0 + " " + b0 + "  ans=" + (answer - memo));
  97. 				}
  98. 			}
  99. 		}
  100. 		return answer;
  101. 	}
  102. }
  103.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: class MappingABC is public, should be declared in a file named MappingABC.java
public class MappingABC {
       ^
Main.java:28: error: cannot find symbol
			Arrays.fill(forbidden[i], 0);
			^
  symbol:   variable Arrays
  location: class MappingABC
Main.java:29: error: cannot find symbol
		Arrays.fill(total, 0);
		^
  symbol:   variable Arrays
  location: class MappingABC
Main.java:58: error: cannot find symbol
			MAX_VAL = max(MAX_VAL, t[i]);
			          ^
  symbol:   method max(int,int)
  location: class MappingABC
4 errors
stdout
copy 
Standard output is empty
https://ideone.com/0xwsbN
language:
Java (12.0.1)
created:
7 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!