結果
問題 | No.1210 XOR Grid |
ユーザー |
|
提出日時 | 2020-08-30 16:33:59 |
言語 | Java (openjdk 23) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 13,811 bytes |
コンパイル時間 | 3,504 ms |
コンパイル使用メモリ | 95,860 KB |
実行使用メモリ | 52,328 KB |
最終ジャッジ日時 | 2024-11-15 11:22:06 |
合計ジャッジ時間 | 9,314 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 57 |
ソースコード
import java.io.OutputStream;import java.io.IOException;import java.io.InputStream;import java.util.Arrays;import java.nio.ByteBuffer;import java.nio.charset.Charset;import java.util.NoSuchElementException;import java.io.OutputStream;import java.nio.CharBuffer;import java.io.IOException;import java.nio.charset.CharsetDecoder;import java.lang.reflect.Field;import java.nio.charset.StandardCharsets;import java.io.UncheckedIOException;import java.util.Objects;import java.io.Writer;import java.io.InputStream;/*** Built using CHelper reloaded plug-in* Actual solution is at the top** @author mikit*/public class Main {public static void main(String[] args) {InputStream inputStream = System.in;OutputStream outputStream = System.out;LightScanner2 in = new LightScanner2(inputStream);LightWriter2 out = new LightWriter2(outputStream);No1210XORGrid solver = new No1210XORGrid();solver.solve(1, in, out);out.close();}static class No1210XORGrid {private static final int MOD = (int) 1e9 + 7;public void solve(int testNumber, LightScanner2 in, LightWriter2 out) {int n = in.ints(), m = in.ints(), x = in.ints();long[] a = in.longs(n), b = in.longs(m);long xor = 0;for (int i = 0; i < n; i++) xor ^= a[i];for (int i = 0; i < m; i++) xor ^= b[i];if (xor != 0) {out.ans(0).ln();return;}ModMath mod = new ModMath();out.ans(mod.pow((1L << x) % MOD, (n - 1L) * (m - 1L))).ln();}}static class ModMath {private static final int DEFAULT_MOD = 1_000_000_007;private final long mod;public ModMath(long mod, boolean unsafe) {/*if (!unsafe && !IntMath.isPrime(mod)) {throw new RuntimeException("This class is designed for primes!");}*/this.mod = mod;}public ModMath(long mod) {this(mod, false);}public ModMath() {this(DEFAULT_MOD, true);}public long mod(long x) {x %= mod;return x < 0 ? x + mod : x;}public long inv(long x) {//return pow(x, mod - 2);return mod(LongEuclidSolver.solve(x, mod).x);}public long pow(long x, long y) {y %= (mod - 1);if (y < 0) {return pow(inv(x), -y);} else if (y == 0) {return 1;} else if (y % 2 == 0) {long z = pow(x, y / 2);return (z * z) % mod;} else {return (x % mod) * pow(x, y - 1) % mod;}}}static class LightScanner2 extends LightScannerAdapter {private static final int BUF_SIZE = 32 * 1024;private final InputStream stream;private final StringBuilder builder = new StringBuilder();private final byte[] buf = new byte[BUF_SIZE];private int ptr;private int len;public LightScanner2(InputStream stream) {this.stream = stream;}private int read() {if (ptr < len) return buf[ptr++];try {ptr = 0;len = stream.read(buf);} catch (IOException ex) {throw new UncheckedIOException(ex);}if (len == -1) return -1;return buf[ptr++];}private void skip() {int b;while (isTokenSeparator(b = read()) && b != -1) ;if (b == -1) throw new NoSuchElementException("EOF");ptr--;}private void loadToken() {builder.setLength(0);skip();for (int b = read(); !isTokenSeparator(b); b = read()) {builder.appendCodePoint(b);}}public String string() {loadToken();return builder.toString();}public int ints() {long x = longs();if (x < Integer.MIN_VALUE || Integer.MAX_VALUE < x) throw new NumberFormatException("Overflow");return (int) x;}public long longs() {skip();int b = read();boolean negate;if (b == '-') {negate = true;b = read();} else negate = false;long x = 0;for (; !isTokenSeparator(b); b = read()) {if ('0' <= b && b <= '9') x = x * 10 + b - '0';else throw new NumberFormatException("Unexpected character '" + b + "'");}return negate ? -x : x;}public void close() {try {stream.close();} catch (IOException e) {throw new UncheckedIOException(e);}}private static boolean isTokenSeparator(int b) {return b < 33 || 126 < b;}}static class LongEuclidSolver {private LongEuclidSolver() {}public static Vec3l solve(long a, long b) {LongEuclidSolver.ReferenceLong p = new LongEuclidSolver.ReferenceLong(), q = new LongEuclidSolver.ReferenceLong();long d = solve(a, b, p, q);return new Vec3l(p.val, q.val, d);}private static long solve(long a, long b, LongEuclidSolver.ReferenceLong p, LongEuclidSolver.ReferenceLong q) {if (b == 0) {p.val = 1;q.val = 0;return a;} else {long d = solve(b, a % b, q, p);q.val -= (a / b) * p.val;return d;}}private static class ReferenceLong {private long val;}}static class Vec3i implements Comparable<Vec3i> {public int x;public int y;public int z;public Vec3i(int x, int y, int z) {this.x = x;this.y = y;this.z = z;}public boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Vec3i vec3i = (Vec3i) o;return x == vec3i.x &&y == vec3i.y &&z == vec3i.z;}public int hashCode() {return Objects.hash(x, y, z);}public String toString() {return "(" + x + ", " + y + ", " + z + ")";}public int compareTo(Vec3i o) {if (x == o.x) {if (y == o.y) {return Integer.compare(z, o.z);}return Integer.compare(y, o.z);}return Integer.compare(x, o.x);}}static interface Verified {}static class LightWriter2 implements AutoCloseable {private static final int BUF_SIZE = 32 * 1024;private static final int BUF_THRESHOLD = 1024;private final OutputStream out;private final byte[] buf = new byte[BUF_SIZE];private int ptr;private final Field fastStringAccess;private boolean autoflush = false;private boolean breaked = true;public LightWriter2(OutputStream out) {this.out = out;Field f;try {f = String.class.getDeclaredField("value");f.setAccessible(true);if (f.getType() != byte[].class) f = null;} catch (ReflectiveOperationException ignored) {f = null;}this.fastStringAccess = f;}public LightWriter2(Writer out) {this.out = new LightWriter2.WriterOutputStream(out);this.fastStringAccess = null;}private void allocate(int n) {if (ptr + n <= BUF_SIZE) return;try {out.write(buf, 0, ptr);ptr = 0;} catch (IOException ex) {throw new UncheckedIOException(ex);}if (BUF_SIZE < n) throw new IllegalArgumentException("Internal buffer exceeded");}public void close() {try {out.write(buf, 0, ptr);ptr = 0;out.flush();out.close();} catch (IOException ex) {throw new UncheckedIOException(ex);}}public LightWriter2 print(char c) {allocate(1);buf[ptr++] = (byte) c;breaked = false;return this;}public LightWriter2 print(String s) {byte[] bytes;if (this.fastStringAccess == null) bytes = s.getBytes();else {try {bytes = (byte[]) fastStringAccess.get(s);} catch (IllegalAccessException ignored) {bytes = s.getBytes();}}int n = bytes.length;if (n <= BUF_THRESHOLD) {allocate(n);System.arraycopy(bytes, 0, buf, ptr, n);ptr += n;return this;}try {out.write(buf, 0, ptr);ptr = 0;out.write(bytes);out.flush();} catch (IOException ex) {throw new UncheckedIOException(ex);}return this;}public LightWriter2 ans(long l) {if (!breaked) {print(' ');}if (l == 0) return print('0');if (l < 0) {print('-');l = -l;}int n = 0;long t = l;while (t > 0) {t /= 10;n++;}allocate(n);for (int i = 1; i <= n; i++) {buf[ptr + n - i] = (byte) (l % 10 + '0');l /= 10;}ptr += n;return this;}public LightWriter2 ans(int i) {if (!breaked) {print(' ');}if (i == 0) return print('0');if (i < 0) {print('-');i = -i;}int n = 0;long t = i;while (t > 0) {t /= 10;n++;}allocate(n);for (int j = 1; j <= n; j++) {buf[ptr + n - j] = (byte) (i % 10 + '0');i /= 10;}ptr += n;return this;}public LightWriter2 ln() {print(System.lineSeparator());breaked = true;if (autoflush) {try {out.flush();} catch (IOException ex) {throw new UncheckedIOException(ex);}}return this;}private static class WriterOutputStream extends OutputStream {final Writer writer;final CharsetDecoder decoder;WriterOutputStream(Writer writer) {this.writer = writer;this.decoder = StandardCharsets.UTF_8.newDecoder();}public void write(int b) throws IOException {writer.write(b);}public void write(byte[] b) throws IOException {writer.write(decoder.decode(ByteBuffer.wrap(b)).array());}public void write(byte[] b, int off, int len) throws IOException {writer.write(decoder.decode(ByteBuffer.wrap(b, off, len)).array());}public void flush() throws IOException {writer.flush();}public void close() throws IOException {writer.close();}}}static abstract class LightScannerAdapter implements AutoCloseable {public abstract String string();public long longs() {return Long.parseLong(string());}public final long[] longs(int length) {long[] res = new long[length];Arrays.setAll(res, ignored -> longs());return res;}public abstract void close();}static class Vec3l implements Comparable<Vec3l> {public long x;public long y;public long z;public Vec3l(long x, long y, long z) {this.x = x;this.y = y;this.z = z;}public boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Vec3i vec3i = (Vec3i) o;return x == vec3i.x &&y == vec3i.y &&z == vec3i.z;}public int hashCode() {return Objects.hash(x, y, z);}public String toString() {return "(" + x + ", " + y + ", " + z + ")";}public int compareTo(Vec3l o) {if (x == o.x) {if (y == o.y) {return Long.compare(z, o.z);}return Long.compare(y, o.z);}return Long.compare(x, o.x);}}}