Submission #3071074
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 | 7665 Byte |
Status | WA |
Exec Time | 262 ms |
Memory | 28588 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 | 151 ms | 24664 KB |
scrambled_01.txt | AC | 145 ms | 24052 KB |
scrambled_02.txt | AC | 146 ms | 26368 KB |
scrambled_03.txt | AC | 239 ms | 27324 KB |
scrambled_04.txt | AC | 220 ms | 26572 KB |
scrambled_05.txt | AC | 164 ms | 24732 KB |
scrambled_06.txt | AC | 159 ms | 24972 KB |
scrambled_07.txt | AC | 166 ms | 25660 KB |
scrambled_08.txt | AC | 183 ms | 25032 KB |
scrambled_09.txt | AC | 160 ms | 23152 KB |
scrambled_10.txt | AC | 167 ms | 22608 KB |
scrambled_11.txt | AC | 150 ms | 24388 KB |
scrambled_12.txt | AC | 160 ms | 26212 KB |
scrambled_13.txt | AC | 166 ms | 25372 KB |
scrambled_14.txt | AC | 251 ms | 25180 KB |
scrambled_15.txt | AC | 246 ms | 23368 KB |
scrambled_16.txt | AC | 168 ms | 25996 KB |
scrambled_17.txt | AC | 177 ms | 27220 KB |
scrambled_18.txt | WA | 197 ms | 27080 KB |
scrambled_19.txt | WA | 192 ms | 25540 KB |
scrambled_20.txt | WA | 163 ms | 25596 KB |
scrambled_21.txt | WA | 174 ms | 26940 KB |
scrambled_22.txt | WA | 178 ms | 25804 KB |
scrambled_23.txt | WA | 170 ms | 26208 KB |
scrambled_24.txt | WA | 230 ms | 25128 KB |
scrambled_25.txt | WA | 170 ms | 25004 KB |
scrambled_26.txt | WA | 191 ms | 26576 KB |
scrambled_27.txt | WA | 216 ms | 26432 KB |
scrambled_28.txt | AC | 117 ms | 26068 KB |
scrambled_29.txt | AC | 110 ms | 23124 KB |
scrambled_30.txt | WA | 111 ms | 23892 KB |
scrambled_31.txt | AC | 205 ms | 28416 KB |
scrambled_32.txt | AC | 101 ms | 22228 KB |
scrambled_33.txt | AC | 139 ms | 25456 KB |
scrambled_34.txt | AC | 153 ms | 23272 KB |
scrambled_35.txt | AC | 160 ms | 22688 KB |
scrambled_36.txt | AC | 165 ms | 24524 KB |
scrambled_37.txt | AC | 168 ms | 24772 KB |
scrambled_38.txt | AC | 164 ms | 25712 KB |
scrambled_39.txt | WA | 245 ms | 26232 KB |
scrambled_40.txt | WA | 181 ms | 26012 KB |
scrambled_41.txt | WA | 262 ms | 25172 KB |
scrambled_42.txt | WA | 208 ms | 26112 KB |
subtask_00.txt | AC | 190 ms | 21860 KB |
subtask_01.txt | AC | 201 ms | 22016 KB |
subtask_02.txt | AC | 151 ms | 23044 KB |
subtask_03.txt | AC | 175 ms | 24656 KB |
subtask_04.txt | AC | 158 ms | 22728 KB |
subtask_05.txt | AC | 168 ms | 26612 KB |
subtask_06.txt | AC | 205 ms | 28588 KB |
subtask_07.txt | AC | 169 ms | 25904 KB |
subtask_08.txt | AC | 227 ms | 24336 KB |
subtask_09.txt | AC | 229 ms | 26500 KB |
subtask_10.txt | AC | 204 ms | 28068 KB |
subtask_11.txt | AC | 206 ms | 24392 KB |
subtask_12.txt | AC | 164 ms | 23508 KB |
subtask_13.txt | AC | 222 ms | 23724 KB |
subtask_14.txt | AC | 117 ms | 25940 KB |
subtask_15.txt | AC | 113 ms | 25428 KB |
subtask_16.txt | WA | 105 ms | 23892 KB |
subtask_17.txt | AC | 136 ms | 23252 KB |
subtask_18.txt | AC | 113 ms | 23380 KB |
subtask_19.txt | AC | 138 ms | 21904 KB |