Submission #3071056
Source Code Expand
// package other2015.utpc2014; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.HashMap; import java.util.InputMismatchException; import java.util.Map; public class Main { static long __startTime = System.currentTimeMillis(); public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); long a = in.nextLong(); long b = in.nextLong(); long x = in.nextLong(); int step = 1<<18; long[] smallStep = new long[step]; smallStep[0] = x<<20; { long last = x; for (int i = 1; i < step; i++) { last = nextNaive(last, b); smallStep[i] = (last<<20)|i; } } Arrays.sort(smallStep); final int MASK = (1<<20)-1; long[] mat2 = generateMat2(b); long[] matGiantStep = MatrixMod2.pow(mat2, 1<<18); { long last = a; for (long n = step ; n < (1L << 36); n += step) { long next = MatrixMod2.mul(matGiantStep, last); long from = next<<20; int fi = Arrays.binarySearch(smallStep, from); if (fi < 0) { fi = -fi-1; } if (fi < smallStep.length && (smallStep[fi]>>20) == next) { long to = (next+1)<<20; long toIdx = Long.MIN_VALUE; long fromIdx = Long.MAX_VALUE; while (fi < smallStep.length && smallStep[fi] < to) { long idx = n - smallStep[fi]&MASK; fromIdx = Math.min(fromIdx, idx); toIdx = Math.max(toIdx, idx); fi++; } long iter = MatrixMod2.mul(MatrixMod2.pow(mat2, fromIdx), a); while (fromIdx < toIdx) { if (iter == x) { out.println(fromIdx); out.flush(); return; } iter = nextNaive(iter, b); fromIdx++; } break; } last = next; } } out.println(-1); out.flush(); } private static boolean verify(long[] mat2, long a, long x) { return MatrixMod2.mul(mat2, a) == x; } static long[] generateMat2(long b) { long[] matA = new long[40]; for (int i = 0; i < 35 ; i++) { matA[i] = 1L<<(i+1); } long[] matB = new long[40]; for (int i = 0; i < 36; i++) { matB[i] = 1L<<i; } matB[39] = 1; long[] matC = new long[40]; for (int i = 0; i < 40 ; i++) { long has = (b & (1L<<i)) >= 1 ? 1 : 0; matC[i] = has<<39; } return MatrixMod2.add(matA, MatrixMod2.mul(matC, matB)); } static long nextNaive(long a, long b) { return (a / 2) ^ ((a % 2) * b); } public static class MatrixMod2 { static long[] e(int n) { long[] mat = new long[n]; for (int i = 0; i < n ; i++) { mat[i] = 1L<<i; } return mat; } static long[] add(long[] a, long[] b) { long[] c = new long[a.length]; for (int i = 0; i < c.length; i++) { c[i] = a[i] ^ b[i]; } return c; } static long[] flip(long[] a) { long[] r = new long[a.length]; for (int i = 0; i < a.length ; i++) { for (int j = 0; j < a.length ; j++) { r[j] |= ((a[i]&(1L<<j))>>j)<<i; } } return r; } static long[] mul(long[] a, long[] b) { long[] res = new long[a.length]; long[] r = flip(b); for (int i = 0; i < a.length ; i++) { for (int j = 0; j < a.length; j++) { long c = Long.bitCount(a[i] & r[j]) % 2; res[i] |= c<<j; } } return res; } static long mul(long[] a, long b) { long r = 0; for (int i = 0; i < a.length; i++) { long c = Long.bitCount(a[i] & b) % 2; r |= c<<i; } return r; } static long[] pow(long[] x, long p) { int n = x.length; long[] ret = e(n); while (p >= 1) { if ((p & 1) == 1) { ret = mul(ret, x); } x = mul(x, x); p >>>= 1; } return ret; } } private static void printTime(String label) { debug(label, System.currentTimeMillis() - __startTime); } private static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } public static class InputReader { private static final int BUFFER_LENGTH = 1 << 12; private InputStream stream; private byte[] buf = new byte[BUFFER_LENGTH]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int next() { if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { return (char) skipWhileSpace(); } public String nextToken() { int c = skipWhileSpace(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { int c = skipWhileSpace(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public double nextDouble() { return Double.valueOf(nextToken()); } int skipWhileSpace() { int c = next(); while (isSpaceChar(c)) { c = next(); } return c; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } } }
Submission Info
Submission Time | |
---|---|
Task | K - 乱数調整 |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 7670 Byte |
Status | WA |
Exec Time | 273 ms |
Memory | 28332 KB |
Judge Result
Set Name | Subtask | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 30 | 0 / 270 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask | subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt |
All | scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, scrambled_33.txt, scrambled_34.txt, scrambled_35.txt, scrambled_36.txt, scrambled_37.txt, scrambled_38.txt, scrambled_39.txt, scrambled_40.txt, scrambled_41.txt, scrambled_42.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
scrambled_00.txt | AC | 154 ms | 24316 KB |
scrambled_01.txt | AC | 140 ms | 22752 KB |
scrambled_02.txt | AC | 163 ms | 22140 KB |
scrambled_03.txt | AC | 186 ms | 22328 KB |
scrambled_04.txt | AC | 157 ms | 26820 KB |
scrambled_05.txt | AC | 165 ms | 24220 KB |
scrambled_06.txt | AC | 151 ms | 22812 KB |
scrambled_07.txt | AC | 164 ms | 24840 KB |
scrambled_08.txt | WA | 161 ms | 26152 KB |
scrambled_09.txt | WA | 164 ms | 24608 KB |
scrambled_10.txt | WA | 181 ms | 25464 KB |
scrambled_11.txt | WA | 257 ms | 26084 KB |
scrambled_12.txt | AC | 162 ms | 25152 KB |
scrambled_13.txt | AC | 153 ms | 24832 KB |
scrambled_14.txt | AC | 266 ms | 24484 KB |
scrambled_15.txt | AC | 248 ms | 23976 KB |
scrambled_16.txt | AC | 180 ms | 24264 KB |
scrambled_17.txt | AC | 179 ms | 27016 KB |
scrambled_18.txt | WA | 214 ms | 26148 KB |
scrambled_19.txt | WA | 189 ms | 26860 KB |
scrambled_20.txt | WA | 179 ms | 28332 KB |
scrambled_21.txt | WA | 195 ms | 24356 KB |
scrambled_22.txt | WA | 162 ms | 22792 KB |
scrambled_23.txt | WA | 157 ms | 23048 KB |
scrambled_24.txt | WA | 273 ms | 23716 KB |
scrambled_25.txt | WA | 169 ms | 26884 KB |
scrambled_26.txt | WA | 181 ms | 25500 KB |
scrambled_27.txt | WA | 210 ms | 26628 KB |
scrambled_28.txt | AC | 117 ms | 26196 KB |
scrambled_29.txt | AC | 113 ms | 23252 KB |
scrambled_30.txt | WA | 114 ms | 23892 KB |
scrambled_31.txt | AC | 186 ms | 23428 KB |
scrambled_32.txt | AC | 112 ms | 23252 KB |
scrambled_33.txt | AC | 138 ms | 24084 KB |
scrambled_34.txt | AC | 164 ms | 23064 KB |
scrambled_35.txt | AC | 162 ms | 23060 KB |
scrambled_36.txt | WA | 162 ms | 22480 KB |
scrambled_37.txt | WA | 170 ms | 24900 KB |
scrambled_38.txt | WA | 158 ms | 25012 KB |
scrambled_39.txt | WA | 249 ms | 24896 KB |
scrambled_40.txt | WA | 191 ms | 25156 KB |
scrambled_41.txt | WA | 241 ms | 25280 KB |
scrambled_42.txt | WA | 250 ms | 26132 KB |
subtask_00.txt | AC | 192 ms | 24624 KB |
subtask_01.txt | AC | 221 ms | 24356 KB |
subtask_02.txt | AC | 173 ms | 23212 KB |
subtask_03.txt | AC | 199 ms | 26120 KB |
subtask_04.txt | AC | 160 ms | 26060 KB |
subtask_05.txt | AC | 161 ms | 27296 KB |
subtask_06.txt | AC | 161 ms | 27816 KB |
subtask_07.txt | AC | 164 ms | 22240 KB |
subtask_08.txt | AC | 167 ms | 27376 KB |
subtask_09.txt | AC | 162 ms | 26832 KB |
subtask_10.txt | AC | 164 ms | 23120 KB |
subtask_11.txt | AC | 162 ms | 26540 KB |
subtask_12.txt | AC | 165 ms | 23500 KB |
subtask_13.txt | AC | 188 ms | 23660 KB |
subtask_14.txt | AC | 121 ms | 25556 KB |
subtask_15.txt | AC | 114 ms | 25172 KB |
subtask_16.txt | WA | 113 ms | 26068 KB |
subtask_17.txt | AC | 136 ms | 22356 KB |
subtask_18.txt | AC | 113 ms | 23892 KB |
subtask_19.txt | AC | 130 ms | 23840 KB |