fork download
  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
stdin
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

Standard output is empty