結果
問題 | No.2129 Perfect Binary Tree...? |
ユーザー |
![]() |
提出日時 | 2022-10-25 12:01:03 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 28,857 bytes |
コンパイル時間 | 4,803 ms |
コンパイル使用メモリ | 92,328 KB |
実行使用メモリ | 53,020 KB |
最終ジャッジ日時 | 2024-07-08 02:29:52 |
合計ジャッジ時間 | 8,971 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | TLE * 1 -- * 28 |
ソースコード
import java.util.*;import java.io.*;class Main {private static final void solve() throws IOException {int n = (1 << ni()) - 1;var g = new ArrayList<ArrayList<Integer>>(n);for (int i = 0; i < n; i++)g.add(new ArrayList<>());for (int i = 2; i <= n; i++) {int u = i - 1, v = i / 2 - 1;g.get(u).add(v);g.get(v).add(u);}var uu = sc.nextCharArray();var vv = sc.nextCharArray();int u = 0, v = 0;for (char c : uu)u = (u << 1) | (c - '0');for (char c : vv)v = (v << 1) | (c - '0');u--;v--;g.get(u).add(v);g.get(v).add(u);long ans = 0L;final int mod = 998244353;var d = new int[n];final int inf = (int) 1e7;var q = new ArrayDeque<Integer>();for (int st = 0; st < n; st++) {Arrays.fill(d, inf);d[st] = 0;q.add(st);while (!q.isEmpty()) {int x = q.remove();for (int i : g.get(x)) {if (d[i] != inf)continue;d[i] = d[x] + 1;q.add(i);}}for (int i : d)ans += i;ans %= mod;}if (ans % 2 != 0)ans += mod;ans /= 2;if (ans < 0)ans += mod;ou.println(ans);}public static void main(String[] args) throws IOException {solve();ou.flush();}private static final int ni() throws IOException {return sc.nextInt();}private static final int[] ni(int n) throws IOException {return sc.nextIntArray(n);}private static final long nl() throws IOException {return sc.nextLong();}private static final long[] nl(int n) throws IOException {return sc.nextLongArray(n);}private static final String ns() throws IOException {return sc.next();}private static final ContestInputStream sc = new ContestInputStream();private static final ContestOutputStream ou = new ContestOutputStream();}class Convolution {private static int primitiveRoot(int m) {if (m == 2)return 1;if (m == 167772161)return 3;if (m == 469762049)return 3;if (m == 754974721)return 11;if (m == 998244353)return 3;int[] divs = new int[20];divs[0] = 2;int cnt = 1;int x = (m - 1) >> 1;while ((x & 1) == 0)x >>= 1;for (int i = 3; i * (long) i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0)x /= i;}}if (x > 1)divs[cnt++] = x;for (int g = 2;; g++) {boolean ok = true;for (int i = 0; i < cnt; i++) {if (pow(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok)return g;}}private static long pow(long x, long n, int m) {if (m == 1)return 0;long r = 1;long y = x % m;while (n > 0) {if ((n & 1) != 0)r = (r * y) % m;y = (y * y) % m;n >>= 1;}return r;}private static int ceilPow2(int n) {int x = 0;while ((1L << x) < n)x++;return x;}private static long garner(long[] c, int[] mods) {int n = c.length + 1;long[] cnst = new long[n];long[] coef = new long[n];Arrays.fill(coef, 1);for (int i = 0; i < n - 1; i++) {int m1 = mods[i];long v = (c[i] - cnst[i] + m1) % m1;v = v * pow(coef[i], m1 - 2, m1) % m1;for (int j = i + 1; j < n; j++) {long m2 = mods[j];cnst[j] = (cnst[j] + coef[j] * v) % m2;coef[j] = coef[j] * m1 % m2;}}return cnst[n - 1];}private static long[] sumE(int mod, int g) {long[] sum_e = new long[30];long[] es = new long[30];long[] ies = new long[30];int cnt2 = Integer.numberOfTrailingZeros(mod - 1);long e = pow(g, (mod - 1) >> cnt2, mod);long ie = pow(e, mod - 2, mod);for (int i = cnt2; i >= 2; i--) {es[i - 2] = e;ies[i - 2] = ie;e = e * e % mod;ie = ie * ie % mod;}long now = 1;for (int i = 0; i < cnt2 - 2; i++) {sum_e[i] = es[i] * now % mod;now = now * ies[i] % mod;}return sum_e;}private static long[] sumIE(int mod, int g) {long[] sum_ie = new long[30];long[] es = new long[30];long[] ies = new long[30];int cnt2 = Integer.numberOfTrailingZeros(mod - 1);long e = pow(g, (mod - 1) >> cnt2, mod);long ie = pow(e, mod - 2, mod);for (int i = cnt2; i >= 2; i--) {es[i - 2] = e;ies[i - 2] = ie;e = e * e % mod;ie = ie * ie % mod;}long now = 1L;for (int i = 0; i < cnt2 - 2; i++) {sum_ie[i] = ies[i] * now % mod;now = now * es[i] % mod;}return sum_ie;}private static void butterflyInv(long[] a, long[] sumIE, int mod) {int n = a.length;int h = ceilPow2(n);for (int ph = h; ph >= 1; ph--) {int w = 1 << (ph - 1), p = 1 << (h - ph);long inow = 1;for (int s = 0; s < w; s++) {int offset = s << (h - ph + 1);for (int i = 0; i < p; i++) {long l = a[i + offset];long r = a[i + offset + p];a[i + offset] = (l + r) % mod;a[i + offset + p] = (mod + l - r) * inow % mod;}int x = Integer.numberOfTrailingZeros(~s);inow = inow * sumIE[x] % mod;}}}private static void butterfly(long[] a, long[] sumE, int mod) {int n = a.length;int h = ceilPow2(n);for (int ph = 1; ph <= h; ph++) {int w = 1 << (ph - 1), p = 1 << (h - ph);long now = 1;for (int s = 0; s < w; s++) {int offset = s << (h - ph + 1);for (int i = 0; i < p; i++) {long l = a[i + offset];long r = a[i + offset + p] * now % mod;a[i + offset] = (l + r) % mod;a[i + offset + p] = (l - r + mod) % mod;}int x = Integer.numberOfTrailingZeros(~s);now = now * sumE[x] % mod;}}}public static long[] convolution(long[] a, long[] b, int mod) {int n = a.length;int m = b.length;if (n == 0 || m == 0)return new long[0];int z = 1 << ceilPow2(n + m - 1);{long[] na = new long[z];long[] nb = new long[z];System.arraycopy(a, 0, na, 0, n);System.arraycopy(b, 0, nb, 0, m);a = na;b = nb;}int g = primitiveRoot(mod);long[] sume = sumE(mod, g);long[] sumie = sumIE(mod, g);butterfly(a, sume, mod);butterfly(b, sume, mod);for (int i = 0; i < z; i++)a[i] = a[i] * b[i] % mod;butterflyInv(a, sumie, mod);a = Arrays.copyOf(a, n + m - 1);long iz = pow(z, mod - 2, mod);for (int i = 0; i < n + m - 1; i++)a[i] = a[i] * iz % mod;return a;}public static long[] convolutionLL(long[] a, long[] b, int mod) {int n = a.length;int m = b.length;if (n == 0 || m == 0)return new long[0];int mod1 = 754974721;int mod2 = 167772161;int mod3 = 469762049;long[] c1 = convolution(a, b, mod1);long[] c2 = convolution(a, b, mod2);long[] c3 = convolution(a, b, mod3);int retSize = c1.length;long[] ret = new long[retSize];int[] mods = { mod1, mod2, mod3, mod };for (int i = 0; i < retSize; ++i)ret[i] = garner(new long[] { c1[i], c2[i], c3[i] }, mods);return ret;}public static long[] inv(long[] f) {final int mod = 998244353;int n = f.length;int c = 1;var g = new long[c];g[0] = pow(f[0], mod - 2, mod);while (c < n) {c <<= 1;var t = Arrays.copyOf(Convolution.convolution(g, Arrays.copyOf(f, c), mod), c);t[0] = mod + 2 - t[0];for (int i = 1; i < c; i++)t[i] = mod - t[i];g = Arrays.copyOf(Convolution.convolution(g, t, mod), c);}return Arrays.copyOf(g, n);}public static long[] convolutionNaive(long[] a, long[] b, int mod) {int n = a.length;int m = b.length;int k = n + m - 1;long[] ret = new long[k];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {ret[i + j] += a[i] * b[j] % mod;ret[i + j] %= mod;}}return ret;}}final class ContestInputStream extends FilterInputStream {protected final byte[] buf;protected int pos = 0;protected int lim = 0;private final char[] cbuf;public ContestInputStream() {super(System.in);this.buf = new byte[1 << 13];this.cbuf = new char[1 << 20];}boolean hasRemaining() throws IOException {if (pos < lim)return true;lim = in.read(buf);pos = 0;return lim > 0;}final int remaining() throws IOException {if (pos >= lim) {lim = in.read(buf);pos = 0;}return lim - pos;}@Overridepublic final int available() throws IOException {if (pos < lim)return lim - pos + in.available();return in.available();}@Overridepublic final long skip(long n) throws IOException {if (pos < lim) {int rem = lim - pos;if (n < rem) {pos += n;return n;}pos = lim;return rem;}return in.skip(n);}@Overridepublic final int read() throws IOException {if (hasRemaining())return buf[pos++];return -1;}@Overridepublic final int read(byte[] b, int off, int len) throws IOException {if (pos < lim) {int rem = Math.min(lim - pos, len);for (int i = 0; i < rem; i++)b[off + i] = buf[pos + i];pos += rem;return rem;}return in.read(b, off, len);}public final char[] readToken() throws IOException {int cpos = 0;int rem;byte b;l: while ((rem = remaining()) > 0) {for (int i = 0; i < rem; i++) {b = buf[pos + i];if (b <= 0x20) {pos += i + 1;cpos += i;if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;break l;}cbuf[cpos + i] = (char) b;}pos += rem;cpos += rem;}char[] arr = new char[cpos];for (int i = 0; i < cpos; i++)arr[i] = cbuf[i];return arr;}public final int readToken(char[] cbuf, int off) throws IOException {int cpos = off;int rem;byte b;l: while ((rem = remaining()) > 0) {for (int i = 0; i < rem; i++) {b = buf[pos + i];if (b <= 0x20) {pos += i + 1;cpos += i;if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;break l;}cbuf[cpos + i] = (char) b;}pos += rem;cpos += rem;}return cpos - off;}public final int readToken(char[] cbuf) throws IOException {return readToken(cbuf, 0);}public final String next() throws IOException {int cpos = 0;int rem;byte b;l: while ((rem = remaining()) > 0) {for (int i = 0; i < rem; i++) {b = buf[pos + i];if (b <= 0x20) {pos += i + 1;cpos += i;if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;break l;}cbuf[cpos + i] = (char) b;}pos += rem;cpos += rem;}return String.valueOf(cbuf, 0, cpos);}public final char[] nextCharArray() throws IOException {return readToken();}public final int nextInt() throws IOException {if (!hasRemaining())return 0;int value = 0;byte b = buf[pos++];if (b == 0x2d) {while (hasRemaining() && (b = buf[pos++]) > 0x20)value = value * 10 - b + 0x30;} else {do {value = value * 10 + b - 0x30;} while (hasRemaining() && (b = buf[pos++]) > 0x20);}if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;return value;}public final long nextLong() throws IOException {if (!hasRemaining())return 0L;long value = 0L;byte b = buf[pos++];if (b == 0x2d) {while (hasRemaining() && (b = buf[pos++]) > 0x20)value = value * 10 - b + 0x30;} else {do {value = value * 10 + b - 0x30;} while (hasRemaining() && (b = buf[pos++]) > 0x20);}if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;return value;}public final char nextChar() throws IOException {if (!hasRemaining())throw new EOFException();final char c = (char) buf[pos++];if (hasRemaining() && buf[pos++] == 0x0d && hasRemaining() && buf[pos] == 0x0a)pos++;return c;}public final float nextFloat() throws IOException {return Float.parseFloat(next());}public final double nextDouble() throws IOException {return Double.parseDouble(next());}public final boolean[] nextBooleanArray(char ok) throws IOException {char[] s = readToken();int n = s.length;boolean[] t = new boolean[n];for (int i = 0; i < n; i++)t[i] = s[i] == ok;return t;}public final boolean[][] nextBooleanMatrix(int h, int w, char ok) throws IOException {boolean[][] s = new boolean[h][];for (int i = 0; i < h; i++) {char[] t = readToken();int n = t.length;s[i] = new boolean[n];for (int j = 0; j < n; j++)s[i][j] = t[j] == ok;}return s;}public final String[] nextStringArray(int len) throws IOException {String[] arr = new String[len];for (int i = 0; i < len; i++)arr[i] = next();return arr;}public final int[] nextIntArray(int len) throws IOException {int[] arr = new int[len];for (int i = 0; i < len; i++)arr[i] = nextInt();return arr;}public final int[] nextIntArray(int len, java.util.function.IntUnaryOperator map) throws IOException {int[] arr = new int[len];for (int i = 0; i < len; i++)arr[i] = map.applyAsInt(nextInt());return arr;}public final long[] nextLongArray(int len, java.util.function.LongUnaryOperator map) throws IOException {long[] arr = new long[len];for (int i = 0; i < len; i++)arr[i] = map.applyAsLong(nextLong());return arr;}public final int[][] nextIntMatrix(int h, int w) throws IOException {int[][] arr = new int[h][w];for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)arr[i][j] = nextInt();return arr;}public final int[][] nextIntMatrix(int h, int w, java.util.function.IntUnaryOperator map) throws IOException {int[][] arr = new int[h][w];for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)arr[i][j] = map.applyAsInt(nextInt());return arr;}public final long[] nextLongArray(int len) throws IOException {long[] arr = new long[len];for (int i = 0; i < len; i++)arr[i] = nextLong();return arr;}public final long[][] nextLongMatrix(int h, int w) throws IOException {long[][] arr = new long[h][w];for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)arr[i][j] = nextLong();return arr;}public final float[] nextFloatArray(int len) throws IOException {float[] arr = new float[len];for (int i = 0; i < len; i++)arr[i] = nextFloat();return arr;}public final double[] nextDoubleArray(int len) throws IOException {double[] arr = new double[len];for (int i = 0; i < len; i++)arr[i] = nextDouble();return arr;}public final char[][] nextCharMatrix(int h, int w) throws IOException {char[][] arr = new char[h][];for (int i = 0; i < h; i++)arr[i] = readToken();return arr;}public final void nextThrow() throws IOException {next();return;}public final void nextThrow(int n) throws IOException {for (int i = 0; i < n; i++)nextThrow();return;}}final class ContestOutputStream extends FilterOutputStream implements Appendable {protected final byte[] buf;protected int pos = 0;public ContestOutputStream() {super(System.out);this.buf = new byte[1 << 13];}@Overridepublic void flush() throws IOException {out.write(buf, 0, pos);pos = 0;out.flush();}void put(byte b) throws IOException {if (pos >= buf.length)flush();buf[pos++] = b;}int remaining() throws IOException {if (pos >= buf.length)flush();return buf.length - pos;}@Overridepublic void write(int b) throws IOException {put((byte) b);}@Overridepublic void write(byte[] b, int off, int len) throws IOException {int o = off;int l = len;while (l > 0) {int rem = Math.min(remaining(), l);for (int i = 0; i < rem; i++)buf[pos + i] = b[o + i];pos += rem;o += rem;l -= rem;}}@Overridepublic ContestOutputStream append(char c) throws IOException {put((byte) c);return this;}@Overridepublic ContestOutputStream append(CharSequence csq, int start, int end) throws IOException {int off = start;int len = end - start;while (len > 0) {int rem = Math.min(remaining(), len);for (int i = 0; i < rem; i++)buf[pos + i] = (byte) csq.charAt(off + i);pos += rem;off += rem;len -= rem;}return this;}@Overridepublic ContestOutputStream append(CharSequence csq) throws IOException {return append(csq, 0, csq.length());}public ContestOutputStream append(char[] arr, int off, int len) throws IOException {int o = off;int l = len;while (l > 0) {int rem = Math.min(remaining(), l);for (int i = 0; i < rem; i++)buf[pos + i] = (byte) arr[o + i];pos += rem;o += rem;l -= rem;}return this;}public ContestOutputStream print(char[] arr) throws IOException {return append(arr, 0, arr.length).newLine();}public ContestOutputStream print(boolean value) throws IOException {if (value)return append("o");return append("x");}public ContestOutputStream println(boolean value) throws IOException {if (value)return append("o\n");return append("x\n");}public ContestOutputStream print(boolean[][] value) throws IOException {final int n = value.length, m = value[0].length;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)print(value[i][j]);newLine();}return this;}public ContestOutputStream print(int value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(int value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream print(long value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(long value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream print(float value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(float value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream print(double value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(double value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream print(char value) throws IOException {return append(value);}public ContestOutputStream println(char value) throws IOException {return append(value).newLine();}public ContestOutputStream print(String value) throws IOException {return append(value);}public ContestOutputStream println(String value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream print(Object value) throws IOException {return append(String.valueOf(value));}public ContestOutputStream println(Object value) throws IOException {return append(String.valueOf(value)).newLine();}public ContestOutputStream printYN(boolean yes) throws IOException {if (yes)return println("Yes");return println("No");}public ContestOutputStream printAB(boolean yes) throws IOException {if (yes)return println("Alice");return println("Bob");}public ContestOutputStream print(CharSequence[] arr) throws IOException {if (arr.length > 0) {append(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').append(arr[i]);}return this;}public ContestOutputStream print(int[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}newLine();return this;}public ContestOutputStream print(int[] arr, int length) throws IOException {if (length > 0)print(arr[0]);for (int i = 1; i < length; i++)append('\u0020').print(arr[i]);newLine();return this;}public ContestOutputStream println(int[] arr) throws IOException {for (int i : arr)print(i).newLine();return this;}public ContestOutputStream println(int[] arr, int length) throws IOException {for (int i = 0; i < length; i++)println(arr[i]);return this;}public ContestOutputStream print(boolean[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}newLine();return this;}public ContestOutputStream print(long[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}newLine();return this;}public ContestOutputStream print(long[] arr, int length) throws IOException {if (length > 0)print(arr[0]);for (int i = 1; i < length; i++)append('\u0020').print(arr[i]);newLine();return this;}public ContestOutputStream println(long[] arr, int length) throws IOException {for (int i = 0; i < length; i++)println(arr[i]);return this;}public ContestOutputStream println(long[] arr) throws IOException {for (long i : arr)print(i).newLine();return this;}public ContestOutputStream print(float[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}return this;}public ContestOutputStream println(float[] arr) throws IOException {for (float i : arr)print(i).newLine();return this;}public ContestOutputStream print(double[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}return newLine();}public ContestOutputStream println(double[] arr) throws IOException {for (double i : arr)print(i).newLine();return this;}public ContestOutputStream print(Object[] arr) throws IOException {if (arr.length > 0) {print(arr[0]);for (int i = 1; i < arr.length; i++)append('\u0020').print(arr[i]);}return newLine();}public ContestOutputStream print(java.util.ArrayList<?> arr) throws IOException {if (!arr.isEmpty()) {final int n = arr.size();print(arr.get(0));for (int i = 1; i < n; i++)print(" ").print(arr.get(i));}return newLine();}public ContestOutputStream println(java.util.ArrayList<?> arr) throws IOException {final int n = arr.size();for (int i = 0; i < n; i++)println(arr.get(i));return this;}public ContestOutputStream println(Object[] arr) throws IOException {for (Object i : arr)print(i).newLine();return this;}public ContestOutputStream newLine() throws IOException {return append(System.lineSeparator());}public ContestOutputStream endl() throws IOException {newLine().flush();return this;}public ContestOutputStream print(int[][] arr) throws IOException {for (int[] i : arr)print(i);return this;}public ContestOutputStream print(long[][] arr) throws IOException {for (long[] i : arr)print(i);return this;}public ContestOutputStream print(char[][] arr) throws IOException {for (char[] i : arr)print(i);return this;}public ContestOutputStream print(Object[][] arr) throws IOException {for (Object[] i : arr)print(i);return this;}public ContestOutputStream println() throws IOException {return newLine();}}