import static java.math.BigInteger.ONE; import static java.math.BigInteger.TEN; import static java.math.BigInteger.ZERO; import java.math.BigInteger; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Scanner; public class fib { private static final BigInteger[] identity = new BigInteger[] { ZERO, ONE, ZERO, ONE }; private static final BigInteger[] transitionOne = new BigInteger[] { ONE, ZERO, ONE, ONE }; private static final String ENTRANCE = "ENTRANCE"; private static BigInteger scope; public static void main(String... args) { Scanner scanner = new Scanner(System.in); BigInteger ending = scanner.nextBigInteger(); scope = TEN.pow(ending.toString(10).length()); scanner.close(); Map<String, BigInteger[]> graph = new HashMap<>(); BigInteger lastDigit = ending.mod(TEN); BigInteger[] start = identity; BigInteger[] shift = identity; BigInteger[] stop = new BigInteger[0]; while (true) { shift = joinScoped(shift, transitionOne); stop = joinScoped(start, shift); if (digit(0, stop[2]).equals(lastDigit)) { String startKey = key(0, start); String stopKey = key(0, stop); graph.put(startKey, shift); if (graph.containsKey(stopKey)) { break; } shift = identity; start = stop; } } HashSet<String> visited = new HashSet<>(); for (int position = 1; position < ending.toString().length(); position++) { BigInteger digit = digit(position, ending); Map<String, BigInteger[]> newGraph = new HashMap<>(); start = identity; shift = graph.get(ENTRANCE); while (true) { stop = joinScoped(start, shift); String startKey = key(position, start); String stopKey = key(position, stop); if (digit(position, stop[2]).equals(digit)) { newGraph.put(startKey, shift); if (newGraph.containsKey(stopKey)) { break; } shift = identity; start = stop; visited.clear(); } else { if (visited.contains(stopKey)) { visited.clear(); break; } else { visited.add(stopKey); } } shift = joinScoped(shift, graph.get(key(position - 1, stop))); } graph = newGraph; if (graph.isEmpty()) { break; } } if (graph.isEmpty()) { System.out.println("NIE"); } else { BigInteger number = graph.get(ENTRANCE)[0]; if (number.compareTo(TEN.pow(100)) < 0) { System.out.println(number); } else { System.out.println("NIE"); } } } private static String key(int position, BigInteger[] node) { return node == identity ? ENTRANCE : "" + node[1].mod(TEN.pow(position + 1)) + ":" + node[2].mod(TEN.pow(position + 1)); } private static BigInteger digit(int position, BigInteger number) { return number.divide(TEN.pow(position)).mod(TEN); } private static BigInteger[] join(BigInteger[] elementA, BigInteger[] elementB) { BigInteger n = elementA[0]; BigInteger fnm1 = elementA[1]; BigInteger fn = elementA[2]; BigInteger fnp1 = elementA[3]; BigInteger k = elementB[0]; BigInteger fkm1 = elementB[1]; BigInteger fk = elementB[2]; BigInteger fkp1 = elementB[3]; BigInteger s = n.add(k); BigInteger fsm1 = fnm1.multiply(fkm1).add(fn.multiply(fk)); BigInteger fs = fn.multiply(fkm1).add(fnp1.multiply(fk)); BigInteger fsp1 = fn.multiply(fk).add(fnp1.multiply(fkp1)); return new BigInteger[] { s, fsm1, fs, fsp1 }; } private static BigInteger[] joinScoped(BigInteger[] elementA, BigInteger[] elementB) { BigInteger[] joined = join(elementA, elementB); return new BigInteger[] { joined[0], joined[1].mod(scope), joined[2].mod(scope), joined[3].mod(scope) }; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | import static java.math.BigInteger.ONE; import static java.math.BigInteger.TEN; import static java.math.BigInteger.ZERO; import java.math.BigInteger; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Scanner; public class fib { private static final BigInteger[] identity = new BigInteger[] { ZERO, ONE, ZERO, ONE }; private static final BigInteger[] transitionOne = new BigInteger[] { ONE, ZERO, ONE, ONE }; private static final String ENTRANCE = "ENTRANCE"; private static BigInteger scope; public static void main(String... args) { Scanner scanner = new Scanner(System.in); BigInteger ending = scanner.nextBigInteger(); scope = TEN.pow(ending.toString(10).length()); scanner.close(); Map<String, BigInteger[]> graph = new HashMap<>(); BigInteger lastDigit = ending.mod(TEN); BigInteger[] start = identity; BigInteger[] shift = identity; BigInteger[] stop = new BigInteger[0]; while (true) { shift = joinScoped(shift, transitionOne); stop = joinScoped(start, shift); if (digit(0, stop[2]).equals(lastDigit)) { String startKey = key(0, start); String stopKey = key(0, stop); graph.put(startKey, shift); if (graph.containsKey(stopKey)) { break; } shift = identity; start = stop; } } HashSet<String> visited = new HashSet<>(); for (int position = 1; position < ending.toString().length(); position++) { BigInteger digit = digit(position, ending); Map<String, BigInteger[]> newGraph = new HashMap<>(); start = identity; shift = graph.get(ENTRANCE); while (true) { stop = joinScoped(start, shift); String startKey = key(position, start); String stopKey = key(position, stop); if (digit(position, stop[2]).equals(digit)) { newGraph.put(startKey, shift); if (newGraph.containsKey(stopKey)) { break; } shift = identity; start = stop; visited.clear(); } else { if (visited.contains(stopKey)) { visited.clear(); break; } else { visited.add(stopKey); } } shift = joinScoped(shift, graph.get(key(position - 1, stop))); } graph = newGraph; if (graph.isEmpty()) { break; } } if (graph.isEmpty()) { System.out.println("NIE"); } else { BigInteger number = graph.get(ENTRANCE)[0]; if (number.compareTo(TEN.pow(100)) < 0) { System.out.println(number); } else { System.out.println("NIE"); } } } private static String key(int position, BigInteger[] node) { return node == identity ? ENTRANCE : "" + node[1].mod(TEN.pow(position + 1)) + ":" + node[2].mod(TEN.pow(position + 1)); } private static BigInteger digit(int position, BigInteger number) { return number.divide(TEN.pow(position)).mod(TEN); } private static BigInteger[] join(BigInteger[] elementA, BigInteger[] elementB) { BigInteger n = elementA[0]; BigInteger fnm1 = elementA[1]; BigInteger fn = elementA[2]; BigInteger fnp1 = elementA[3]; BigInteger k = elementB[0]; BigInteger fkm1 = elementB[1]; BigInteger fk = elementB[2]; BigInteger fkp1 = elementB[3]; BigInteger s = n.add(k); BigInteger fsm1 = fnm1.multiply(fkm1).add(fn.multiply(fk)); BigInteger fs = fn.multiply(fkm1).add(fnp1.multiply(fk)); BigInteger fsp1 = fn.multiply(fk).add(fnp1.multiply(fkp1)); return new BigInteger[] { s, fsm1, fs, fsp1 }; } private static BigInteger[] joinScoped(BigInteger[] elementA, BigInteger[] elementB) { BigInteger[] joined = join(elementA, elementB); return new BigInteger[] { joined[0], joined[1].mod(scope), joined[2].mod(scope), joined[3].mod(scope) }; } } |