結果
| 問題 | No.872 All Tree Path |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2019-08-30 22:49:09 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 41,369 bytes |
| コンパイル時間 | 3,455 ms |
| コンパイル使用メモリ | 104,384 KB |
| 最終ジャッジ日時 | 2024-11-14 21:36:17 |
| 合計ジャッジ時間 | 4,287 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Main.java:558: warning: [removal] finalize() in Object has been deprecated and marked for removal
protected void finalize() throws Throwable {
^
Main.java:560: warning: [removal] finalize() in Object has been deprecated and marked for removal
super.finalize();
^
1 error
2 warnings
ソースコード
import java.awt.Point;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.Serializable;
import java.util.AbstractList;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.RandomAccess;
import java.util.function.BinaryOperator;
import java.util.function.UnaryOperator;
public class Main_Short implements Runnable{
/** デバッグ用コードのお供に */
private static boolean DEBUG = false;
/** 確保するメモリの大きさ(単位: MB)*/
private static final long MEMORY = 64;
private final FastIO io;
private static class Edge {
int src, dest, weight;
Edge(int u, int v, int w) {
src = u;
dest = v;
weight = w;
}
}
private void solve(FastIO io) {
/*
* author: 31536000
* yukicoder contest 221 C問題
* 考察メモ
* 辺の左にある頂点集合×右にある頂点集合だけ、その辺が計算対象になる
*/
int N = io.nextInt();
ArrayList<ArrayList<Edge>> graph = new ArrayList<>(N);
for (@SuppressWarnings("unused")final int i : IntRange.open(N)) graph.add(new ArrayList<Edge>());
int[] set = new int[N], node = new int[N];
Edge[] parent = new Edge[N];
Arrays.fill(node, 0);
Arrays.fill(set, 1);
for (@SuppressWarnings("unused")final int i : IntRange.open(N - 1)) {
int u = io.nextInt() - 1, v = io.nextInt() - 1, w = io.nextInt();
graph.get(u).add(new Edge(u, v, w));
graph.get(v).add(new Edge(v, u, w));
}
long ans = 0;
BreadthFirstSearch<Integer> bfs = new BreadthFirstSearch<Integer>(), bfs2 = new BreadthFirstSearch<Integer>();
bfs.push(0);
for (final int i : bfs) {
if (graph.get(i).size() == 1) bfs2.push(i);
for (final Edge j : graph.get(i)) if (bfs.push(j.dest)) {
parent[j.dest] = j;
++ node[i];
}
}
for (final int i : bfs2) {
if (i == 0) continue;
ans += (long)parent[i].weight * set[i] * (N - set[i]);
set[parent[i].src] += set[i];
if (-- node[parent[i].src] <= 0) bfs2.push(parent[i].src);
}
io.println(ans * 2);
}
public static void main(String[] args) {
Thread.setDefaultUncaughtExceptionHandler((t, e) -> e.printStackTrace());
new Thread(null, new Main_Short(), "", MEMORY * 1048576).start();
}
public Main_Short() {
io = new FastIO();
//assert (DEBUG = true) | true; // yukicoderだと-eaが付いてるので正しく動かないことに注意
if (DEBUG) {
io.setAutoFlush(true);
io.println("debug mode");
}
}
@Override
public void run() {
solve(io);
io.flush();
}
// 以下、ライブラリ
/**
* 幅優先探索を自動的に行うライブラリです。
* @author 31536000
*
* @param <T> 幅優先探索の対象となる型
*/
public static class BreadthFirstSearch<T> implements Iterable<T>, Iterator<T>{
CircularArray<Deque<T>> queue;
HashSet<T> hash;
int size;
/**
* キューを1個用いるBFSを用意します。
*/
public BreadthFirstSearch() {
this(1);
}
/**
* キューをn個用いるBFSを用意します。
* @param n 使うキューの数
*/
public BreadthFirstSearch(int n) {
queue = new CircularArray<Deque<T>>(n);
for (int i = 0;i < n;++ i) queue.set(i, new ArrayDeque<T>());
hash = new HashSet<T>();
size = 0;
}
/**
* キューを1個用いて、最初に調べる場所がtのBFSを作成します。
* @param t 最初に調べる値
*/
public BreadthFirstSearch(T t) {
this(1, t);
}
/**
* キューをn個用いて、最初に調べる場所がtのBFSを作成します。
* @param n 使うキューの数
* @param t 最初に調べる値
*/
public BreadthFirstSearch(int n, T t) {
this(n);
push(t);
}
/**
* 第n番目のキューに新しくtを調べる対象に追加します。
* @param n 使うキューの場所(0はstackとして処理される)
* @param t 調べる値
* @return 既にtを調べたことがあるならfalse、まだ調べてないならtrue
*/
public boolean push(int n, T t) {
if (n < 0 || n > queue.size()) throw new IndexOutOfBoundsException();
if (n == 0) { // stackとして使う
Deque<T> que = queue.front();
if (!hash.add(t)) return false;
que.addFirst(t);
} else { // queueとして使う
Deque<T> que = queue.get(n - 1);
if (!hash.add(t)) return false;
que.addLast(t);
}
++ size;
return true;
}
/**
* 1番目のキューに新しくtを調べる対象に追加します。
* @param t 調べる値
* @return 既にtを調べたことがあるならfalse、まだ調べてないならtrue
*/
public boolean push(T t) {
if (!hash.add(t)) return false;
queue.front().addLast(t);
++ size;
return true;
}
/**
* 既にその要素を調べているか返します。
* @param t 調べる値
* @return 既に調べていたらtrue
*/
public boolean contains(T t) {
return hash.contains(t);
}
/**
* BFSを初期化します。
*/
public void clear() {
for (Deque<T> i : queue) i.clear();
hash.clear();
size = 0;
}
@Override
public Iterator<T> iterator() {
return this;
}
@Override
public boolean hasNext() {
return size > 0;
}
@Override
public T next() {
if (size <= 0) throw new NoSuchElementException();
while (queue.front().isEmpty()) queue.rotateNext();
-- size;
return queue.front().pollFirst();
}
}
/**
* 端がもう片側の端と繋がり、循環する固定長配列を提供します。
* @author 31536000
*
* @param <T> 配列の型
*/
public static class CircularArray<T> extends Array<T>{
private static final long serialVersionUID = 8755553665486205607L;
private int first = 0;
/**
* 長さsizeで、初期の要素が全てnullの配列を作成します。
* @param size 要素数
*/
public CircularArray(int size) {
super(size);
}
/**
* arrayを固定長配列として扱います。
* @param array 元となる配列
*/
public CircularArray(T[] array) {
super(array);
}
/**
* index番目の要素を取得します。
* @param index 取得する要素のインデックス
* @return index番目の要素
*/
private int getIndex(int index) {
index -= first;
if (index >= size()) index %= size();
else if (index < 0) index = size() + index % size();
return index;
}
/**
* 先頭の要素を上書きします。<br>
* この関数はset(0, value)と同一です。
* @param value 上書きする要素
*/
public void setFront(T value) {
super.set(first, value);
}
/**
* index番目の要素を上書きします。<br>
* この時、indexは要素数を法とする自然数上に丸められます。
* @param index 上書きする場所
* @param value 上書きする値
*/
@Override
public T set(int index, T value) {
return super.set(getIndex(index), value);
}
/**
* 末尾の要素を上書きします。<br>
* この関数はset(-1, value)と同一です。
* @param value 上書きする要素
*/
public void setBack(T value) {
super.set(first == 0 ? size() - 1 : first - 1, value);
}
/**
* index番目の要素を取得します。<br>
* この時、indexは要素数を法とする自然数上に丸められます。
* @param index 取得する場所
* @return index番目の要素
*/
@Override
public T get(int index) {
return super.get(getIndex(index));
}
/**
* 先頭の要素を取得します。<br>
* この関数はget(0)と同一です。
* @return 先頭の要素
*/
@Override
public T front() {
return super.get(first);
}
/**
* 末尾の要素を取得します。<br>
* この関数はget(-1)と同一です。
* @return 末尾の要素
*/
@Override
public T back() {
return super.get(first == 0 ? size() - 1 : first - 1);
}
/**
* 先頭の位置をずらします。<br>
* 例えばrotateが1の時、get(1)で取り出せていた要素は次からget(0)で取り出せるようになります。
* @param rotate ずらす量
*/
public void rotate(int rotate) {
first = getIndex(rotate);
}
/**
* 先頭の位置を一つ後にずらします。<br>
* この関数はrotate(1)と同一です。
*/
public void rotateNext() {
if (++first >= size()) first = 0;
}
/**
* 先頭の位置を一つ前にずらします。<br>
* この関数はrotate(-1)と同一です。
*/
public void rotatePrevious() {
if (--first < 0) first = size() - 1;
}
private class Iter implements Iterator<T> {
private int index;
private int count;
Iter() {
index = first;
count = 0;
}
@Override
public boolean hasNext() {
return count < size();
}
@Override
public T next() {
T ret = get(index);
if (++index >= size()) index = 0;
++ count;
return ret;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<T> iterator() {
return new Iter();
}
}
public static class FastIO {
private final InputStream in;
private final byte[] buffer = new byte[1024];
private int read = 0;
private int length = 0;
public final PrintWriter out;
public final PrintWriter err;
private boolean autoFlush = false;
public FastIO() {
this(System.in, System.out, System.err);
}
public FastIO(InputStream in, PrintStream out, PrintStream err) {
this.in = in;
this.out = new PrintWriter(out, false);
this.err = new PrintWriter(err, false);
}
public void setAutoFlush(boolean flush) {
autoFlush = flush;
}
private boolean hasNextByte() {
if (read < length) return true;
read = 0;
try {
length = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return length > 0;
}
private int readByte() {
return hasNextByte() ? buffer[read++] : -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private static boolean isNumber(int c) {
return '0' <= c && c <= '9';
}
public boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[read])) read++;
return hasNextByte();
}
public char nextChar() {
if (!hasNextByte()) throw new NoSuchElementException();
return (char)readByte();
}
public char[][] nextChar(int height) {
char[][] ret = new char[height][];
for (int i = 0;i < ret.length;++ i) ret[i] = next().toCharArray();
return ret;
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b;
while (isPrintableChar(b = readByte())) sb.appendCodePoint(b);
return sb.toString();
}
public String nextLine() {
StringBuilder sb = new StringBuilder();
int b;
while(!isPrintableChar(b = readByte()));
do sb.appendCodePoint(b); while(isPrintableChar(b = readByte()) || b == ' ');
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (!isNumber(b)) throw new NumberFormatException();
while (true) {
if (isNumber(b)) {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) return minus ? -n : n;
else throw new NumberFormatException();
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public int[] nextInt(int width) {
int[] ret = new int[width];
for (int i = 0;i < width;++ i) ret[i] = nextInt();
return ret;
}
public int[] nextInts() {
return nextInts(" ");
}
public int[] nextInts(String parse) {
String[] get = nextLine().split(parse);
int[] ret = new int[get.length];
for (int i = 0;i < ret.length;++ i) ret[i] = Integer.valueOf(ret[i]);
return ret;
}
public long[] nextLong(int width) {
long[] ret = new long[width];
for (int i = 0;i < width;++ i) ret[i] = nextLong();
return ret;
}
public long[] nextLongs() {
return nextLongs(" ");
}
public long[] nextLongs(String parse) {
String[] get = nextLine().split(parse);
long[] ret = new long[get.length];
for (int i = 0;i < ret.length;++ i) ret[i] = Long.valueOf(ret[i]);
return ret;
}
public int[][] nextInt(int width, int height) {
int[][] ret = new int[height][width];
for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[i][j] = nextInt();
return ret;
}
public long[][] nextLong(int width, int height) {
long[][] ret = new long[height][width];
for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[j][i] = nextLong();
return ret;
}
public boolean[] nextBoolean(char T) {
char[] s = next().toCharArray();
boolean[] ret = new boolean[s.length];
for (int i = 0;i < ret.length;++ i) ret[i] = s[i] == T;
return ret;
}
public boolean[][] nextBoolean(char T, int height) {
boolean[][] ret = new boolean[height][];
for (int i = 0;i < ret.length;++ i) {
char[] s = next().toCharArray();
ret[i] = new boolean[s.length];
for (int j = 0;j < ret[i].length;++ j) ret[i][j] = s[j] == T;
}
return ret;
}
public Point nextPoint() {
return new Point(nextInt(), nextInt());
}
public Point[] nextPoint(int width) {
Point[] ret = new Point[width];
for (int i = 0;i < width;++ i) ret[i] = nextPoint();
return ret;
}
@Override
protected void finalize() throws Throwable {
try {
super.finalize();
} finally {
in.close();
out.close();
err.close();
}
}
public boolean print(boolean b) {
out.print(b);
if (autoFlush) flush();
return b;
}
public Object print(boolean b, Object t, Object f) {
return b ? print(t) : print(f);
}
public char print(char c) {
out.print(c);
if (autoFlush) flush();
return c;
}
public char[] print(char[] s) {
out.print(s);
return s;
}
public double print(double d) {
out.print(d);
if (autoFlush) flush();
return d;
}
public double print(double d, int length) {
if (d < 0) {
out.print('-');
d = -d;
}
d += Math.pow(10, -length) / 2;
out.print((long)d);
out.print('.');
d -= (long)d;
for (int i = 0;i < length;++ i) {
d *= 10;
out.print((int)d);
d -= (int)d;
}
if (autoFlush) flush();
return d;
}
public float print(float f) {
out.print(f);
if (autoFlush) flush();
return f;
}
public int print(int i) {
out.print(i);
if (autoFlush) flush();
return i;
}
public long print(long l) {
out.print(l);
if (autoFlush) flush();
return l;
}
public Object print(Object obj) {
if (obj.getClass().isArray()) {
if (obj instanceof boolean[][]) print(obj, "\n", " ");
else if (obj instanceof byte[][]) print(obj, "\n", " ");
else if (obj instanceof short[][]) print(obj, "\n", " ");
else if (obj instanceof int[][]) print(obj, "\n", " ");
else if (obj instanceof long[][]) print(obj, "\n", " ");
else if (obj instanceof float[][]) print(obj, "\n", " ");
else if (obj instanceof double[][]) print(obj, "\n", " ");
else if (obj instanceof char[][]) print(obj, "\n", " ");
else if (obj instanceof Object[][]) print(obj, "\n", " ");
else print(obj, " ");
} else {
out.print(obj);
if (autoFlush) flush();
}
return obj;
}
public String print(String s) {
out.print(s);
if (autoFlush) flush();
return s;
}
public Object print(Object array, String... parse) {
print(array, 0, parse);
if (autoFlush) flush();
return array;
}
private Object print(Object array, int check, String... parse) {
if (check >= parse.length) {
if (array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
print(array);
return array;
}
String str = parse[check];
if (array instanceof Object[]) {
Object[] obj = (Object[]) array;
if (obj.length == 0) return array;
print(obj[0], check + 1, parse);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i], check + 1, parse);
}
return array;
}
if (array instanceof Collection) {
Iterator<?> iter = ((Collection<?>)array).iterator();
if (!iter.hasNext()) return array;
print(iter.next(), check + 1, parse);
while(iter.hasNext()) {
print(str);
print(iter.next(), check + 1, parse);
}
return array;
}
if (!array.getClass().isArray()) throw new IllegalArgumentException("not equal dimension");
if (check != parse.length - 1) throw new IllegalArgumentException("not equal dimension");
if (array instanceof boolean[]) {
boolean[] obj = (boolean[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof byte[]) {
byte[] obj = (byte[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
return array;
} else if (array instanceof short[]) {
short[] obj = (short[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof int[]) {
int[] obj = (int[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof long[]) {
long[] obj = (long[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof float[]) {
float[] obj = (float[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof double[]) {
double[] obj = (double[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else if (array instanceof char[]) {
char[] obj = (char[]) array;
if (obj.length == 0) return array;
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(str);
print(obj[i]);
}
} else throw new AssertionError();
return array;
}
public Object[] print(String parse, Object... args) {
print(args[0]);
for (int i = 1;i < args.length;++ i) {
print(parse);
print(args[i]);
}
return args;
}
public Object[] printf(String format, Object... args) {
out.printf(format, args);
if (autoFlush) flush();
return args;
}
public Object printf(Locale l, String format, Object... args) {
out.printf(l, format, args);
if (autoFlush) flush();
return args;
}
public void println() {
out.println();
if (autoFlush) flush();
}
public boolean println(boolean b) {
out.println(b);
if (autoFlush) flush();
return b;
}
public Object println(boolean b, Object t, Object f) {
return b ? println(t) : println(f);
}
public char println(char c) {
out.println(c);
if (autoFlush) flush();
return c;
}
public char[] println(char[] s) {
out.println(s);
if (autoFlush) flush();
return s;
}
public double println(double d) {
out.println(d);
if (autoFlush) flush();
return d;
}
public double println(double d, int length) {
print(d, length);
println();
return d;
}
public float println(float f) {
out.println(f);
if (autoFlush) flush();
return f;
}
public int println(int i) {
out.println(i);
if (autoFlush) flush();
return i;
}
public long println(long l) {
out.println(l);
if (autoFlush) flush();
return l;
}
public Object println(Object obj) {
print(obj);
println();
return obj;
}
public String println(String s) {
out.println(s);
if (autoFlush) flush();
return s;
}
public Object println(Object array, String... parse) {
print(array, parse);
println();
return array;
}
public void flush() {
out.flush();
err.flush();
}
}
public enum BoundType {
CLOSED, OPEN;
}
public static class IntRange implements Iterable<Integer>{
protected final int lower;
protected final int upper;
protected final UnaryOperator<Integer> func;
private final boolean useFastIter;
private static class Next implements UnaryOperator<Integer> {
@Override
public Integer apply(Integer value) {
return value + 1;
}
}
private IntRange(int lower, int upper, UnaryOperator<Integer> func, boolean useFast) {
this.lower = lower;
this.upper = upper;
this.func = func;
this.useFastIter = useFast;
}
protected IntRange() {
this(Integer.MAX_VALUE, Integer.MIN_VALUE, new Next(), true);
}
protected IntRange(UnaryOperator<Integer> func) {
this(0, 0, func, false);
}
public static IntRange range(int lower, BoundType lowerType, int upper, BoundType upperType) {
if (lower > upper) return new IntRange();
if (lowerType == BoundType.OPEN) ++ lower;
if (upperType == BoundType.OPEN) -- upper;
return new IntRange(lower, upper, new Next(), true);
}
public static IntRange range(int lower, BoundType lowerType, int upper, BoundType upperType, UnaryOperator<Integer> func) {
if (lower > upper) return new IntRange(func);
if (lowerType == BoundType.OPEN) ++ lower;
if (upperType == BoundType.OPEN) -- upper;
return new IntRange(lower, upper, func, false);
}
public static IntRange open(int lower, int upper) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN);
}
public static IntRange open(int lower, int upper, UnaryOperator<Integer> func) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN, func);
}
public static IntRange open(int upper) {
return range(0, BoundType.CLOSED, upper, BoundType.OPEN);
}
public static IntRange open(int upper, UnaryOperator<Integer> func) {
return range(0, BoundType.CLOSED, upper, BoundType.OPEN, func);
}
public static IntRange openClosed(int lower, int upper) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED);
}
public static IntRange openClosed(int lower, int upper, UnaryOperator<Integer> func) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED, func);
}
public static IntRange closedOpen(int lower, int upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN);
}
public static IntRange closedOpen(int lower, int upper, UnaryOperator<Integer> func) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, func);
}
public static IntRange closed(int lower, int upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static IntRange closed(int lower, int upper, UnaryOperator<Integer> func) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static IntRange closed(int upper) {
return range(0, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static IntRange closed(int upper, UnaryOperator<Integer> func) {
return range(0, BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static IntRange singleton(int value) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED);
}
public static IntRange singleton(int value, UnaryOperator<Integer> func) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED, func);
}
public boolean contains(int value) {
return lower <= value && value <= upper;
}
private class FastIter implements Iterator<Integer> {
int now;
public FastIter() {
now = lower;
}
@Override
public final boolean hasNext() {
return now <= upper;
}
@Override
public final Integer next() {
return now++;
}
@Override
public final void remove() {
throw new UnsupportedOperationException();
}
}
private class Iter implements Iterator<Integer> {
int now;
public Iter() {
now = lower;
}
@Override
public final boolean hasNext() {
return now <= upper;
}
@Override
public final Integer next() {
int ret = now;
now = func.apply(now);
return ret;
}
@Override
public final void remove() {
throw new UnsupportedOperationException();
}
}
public Iterator<Integer> iterator() {
return useFastIter ? new FastIter() : new Iter();
}
public int getDistance() {
return upper - lower + 1;
}
public int getClosedLower() {
return lower;
}
public int getOpenLower() {
return lower - 1;
}
public int getClosedUpper() {
return upper;
}
public int getOpenUpper() {
return upper + 1;
}
@Override
public String toString() {
if (lower > upper) return "()";
return ("[" + lower + ".." + upper + "]");
}
}
public interface Associative<T> extends BinaryOperator<T>{
public default T hyper(T element, int repeat) {
if (repeat < 1) throw new IllegalArgumentException("undefined operation");
T ret = element;
-- repeat;
for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul);
return ret;
}
}
public interface Inverse<T> extends BinaryOperator<T>{
public T inverse(T element);
}
public interface Commutative<T> extends BinaryOperator<T>{
}
public interface Unit<T> extends BinaryOperator<T>{
public T unit();
}
public interface Group<T> extends Monoid<T>, Inverse<T>{
@Override
public default T hyper(T element, int repeat) {
T ret = unit();
if (repeat < 0) {
repeat = -repeat;
for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul);
return inverse(ret);
}
for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul);
return ret;
}
}
public interface Monoid<T> extends Associative<T>, Unit<T> {
@Override
public default T hyper(T element, int repeat) {
if (repeat < 0) throw new IllegalArgumentException("undefined operation");
T ret = unit();
for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul);
return ret;
}
}
public interface CommutativeMonoid<T> extends Monoid<T>, Commutative<T> {
}
public interface Abelian<T> extends Group<T>, CommutativeMonoid<T> {
}
public interface Semiring<T, A extends CommutativeMonoid<T>, M extends Monoid<T>> {
public A getAddition();
public M getMultiplication();
}
public interface Ring<T, A extends Abelian<T>, M extends Monoid<T>> extends Semiring<T, A, M>{
}
public interface CommutativeRing<T, A extends Abelian<T>, M extends CommutativeMonoid<T>> extends Ring<T, A, M>{
}
public static class ModInteger extends Number implements CommutativeRing<ModInteger, Abelian<ModInteger>, CommutativeMonoid<ModInteger>>{
private static final long serialVersionUID = -8595710127161317579L;
private final int mod;
private int num;
private final Addition add;
private final Multiplication mul;
private class Addition implements Abelian<ModInteger> {
@Override
public ModInteger unit() {
return new ModInteger(mod, 0);
}
@Override
public ModInteger inverse(ModInteger element) {
return new ModInteger(element, element.mod - element.num);
}
@Override
public ModInteger apply(ModInteger left, ModInteger right) {
return new ModInteger(left).addEqual(right);
}
}
private class Multiplication implements Abelian<ModInteger> {
@Override
public ModInteger unit() {
return new ModInteger(mod, 1);
}
@Override
public ModInteger apply(ModInteger left, ModInteger right) {
return new ModInteger(left).multiplyEqual(right);
}
@Override
public ModInteger inverse(ModInteger element) {
return new ModInteger(element, element.inverse(element.num));
}
}
public ModInteger(int mod) {
this.mod = mod;
num = 0;
add = new Addition();
mul = new Multiplication();
}
public ModInteger(int mod, int num) {
this.mod = mod;
this.num = validNum(num);
add = new Addition();
mul = new Multiplication();
}
public ModInteger(ModInteger n) {
mod = n.mod;
num = n.num;
add = n.add;
mul = n.mul;
}
private ModInteger(ModInteger n, int num) {
mod = n.mod;
this.num = num;
add = n.add;
mul = n.mul;
}
private int validNum(int n) {
n %= mod;
if (n < 0) n += mod;
return n;
}
private int validNum(long n) {
n %= mod;
if (n < 0) n += mod;
return (int)n;
}
protected int inverse(int n) {
int m = mod, u = 0, v = 1, t;
while(n != 0) {
t = m / n;
m -= t * n;
u -= t * v;
if (m != 0) {
t = n / m;
n -= t * m;
v -= t * u;
} else {
v %= mod;
if (v < 0) v += mod;
return v;
}
}
u %= mod;
if (u < 0) u += mod;
return u;
}
public boolean isPrime(int n) {
if ((n & 1) == 0) return false;
for (int i = 3, j = 8, k = 9;k <= n;i += 2, k += j += 8) if (n % i == 0) return false;
return true;
}
@Override
public int intValue() {
return num;
}
@Override
public long longValue() {
return num;
}
@Override
public float floatValue() {
return num;
}
@Override
public double doubleValue() {
return num;
}
public ModInteger add(int n) {
return new ModInteger(this).addEqual(n);
}
public ModInteger add(long n) {
return new ModInteger(this).addEqual(n);
}
public ModInteger add(ModInteger n) {
return new ModInteger(this).addEqual(n);
}
public ModInteger addEqual(int n) {
num = validNum(num + n);
return this;
}
public ModInteger addEqual(long n) {
num = validNum(num + n);
return this;
}
public ModInteger addEqual(ModInteger n) {
if ((num += n.num) >= mod) num -= mod;
return this;
}
public ModInteger subtract(int n) {
return new ModInteger(this).subtractEqual(n);
}
public ModInteger subtract(long n) {
return new ModInteger(this).subtractEqual(n);
}
public ModInteger subtract(ModInteger n) {
return new ModInteger(this).subtractEqual(n);
}
public ModInteger subtractEqual(int n) {
num = validNum(num - n);
return this;
}
public ModInteger subtractEqual(long n) {
num = validNum(num - n);
return this;
}
public ModInteger subtractEqual(ModInteger n) {
if ((num -= n.num) < 0) num += mod;
return this;
}
public ModInteger multiply(int n) {
return new ModInteger(this).multiplyEqual(n);
}
public ModInteger multiply(long n) {
return new ModInteger(this).multiplyEqual(n);
}
public ModInteger multiply(ModInteger n) {
return new ModInteger(this).multiplyEqual(n);
}
public ModInteger multiplyEqual(int n) {
num = (int)((long)num * n % mod);
if (num < 0) num += mod;
return this;
}
public ModInteger multiplyEqual(long n) {
return multiplyEqual((int) (n % mod));
}
public ModInteger multiplyEqual(ModInteger n) {
num = (int)((long)num * n.num % mod);
return this;
}
public ModInteger divide(int n) {
return new ModInteger(this).divideEqual(n);
}
public ModInteger divide(long n) {
return new ModInteger(this).divideEqual(n);
}
public ModInteger divide(ModInteger n) {
return new ModInteger(this).divideEqual(n);
}
public ModInteger divideEqual(int n) {
num = (int)((long)num * inverse(validNum(n)) % mod);
return this;
}
public ModInteger divideEqual(long n) {
return divideEqual((int)(n % mod));
}
public ModInteger divideEqual(ModInteger n) {
num = (int)((long)num * n.inverse(n.num) % mod);
return this;
}
public ModInteger pow(int n) {
return new ModInteger(this).powEqual(n);
}
public ModInteger pow(long n) {
return new ModInteger(this).powEqual(n);
}
public ModInteger pow(ModInteger n) {
return new ModInteger(this).powEqual(n);
}
public ModInteger powEqual(int n) {
long ans = 1, num = this.num;
if (n < 0) {
n = -n;
while (n != 0) {
if ((n & 1) != 0) ans = ans * num % mod;
n >>>= 1;
num = num * num % mod;
}
this.num = inverse((int)ans);
return this;
}
while (n != 0) {
if ((n & 1) != 0) ans = ans * num % mod;
n >>>= 1;
num = num * num % mod;
}
this.num = (int)ans;
return this;
}
public ModInteger powEqual(long n) {
return powEqual((int)(n % (mod - 1)));
}
public ModInteger powEqual(ModInteger n) {
long num = this.num;
this.num = 1;
int mul = n.num;
while (mul != 0) {
if ((mul & 1) != 0) this.num *= num;
mul >>>= 1;
num *= num;
num %= mod;
}
return this;
}
public ModInteger equal(int n) {
num = validNum(n);
return this;
}
public ModInteger equal(long n) {
num = validNum(n);
return this;
}
public ModInteger equal(ModInteger n) {
num = n.num;
return this;
}
public int toInt() {
return num;
}
public int getMod() {
return mod;
}
@Override
public boolean equals(Object x) {
if (x instanceof ModInteger) return ((ModInteger)x).num == num && ((ModInteger)x).mod == mod;
return false;
}
@Override
public int hashCode() {
return num ^ mod;
}
@Override
public String toString() {
return String.valueOf(num);
}
@Deprecated
public String debug() {
int min = num, ans = 1;
for (int i = 2;i < min;++ i) {
int tmp = multiply(i).num;
if (min > tmp) {
min = tmp;
ans = i;
}
}
return min + "/" + ans;
}
@Override
public Addition getAddition() {
return add;
}
@Override
public Multiplication getMultiplication() {
return mul;
}
}
public static class ModUtility {
private final int mod, totient;
private int[] fact, inv, invfact;
public ModUtility(int mod) {
this(mod, 2);
}
public ModUtility(int mod, int calc) {
if (mod <= 0) throw new IllegalArgumentException("illegal mod: " + mod);
this.mod = mod;
int totient = mod;
for (int i = 2;i * i <= mod;++ i) {
if (mod % i == 0) {
totient = totient / i * (i - 1);
while ((mod %= i) % i == 0);
}
}
this.totient = totient;
precalc(calc);
}
public void precalc(int calc) {
if (calc < 2) calc = 2;
fact = new int[calc];
inv = new int[calc];
invfact = new int[calc];
fact[0] = invfact[0] = fact[1] = invfact[1] = inv[1] = 1;
for (int i = 2;i < calc;++ i) {
fact[i] = (int)((long)fact[i - 1] * i % mod);
inv[i] = (int)(mod - (long)inv[mod % i] * (mod / i) % mod);
invfact[i] = (int)((long)invfact[i - 1] * inv[i] % mod);
}
}
public ModInteger create() {
return create(0);
}
public ModInteger create(int n) {
return new ModInt(n);
}
private class ModInt extends ModInteger {
private static final long serialVersionUID = -2435281861935422575L;
public ModInt(int n) {
super(mod, n);
}
@Override
protected int inverse(int n) {
return ModUtility.this.inverse(n);
}
}
public int inverse(int n) {
try {
if (inv.length > n) return inv[n];
int m = mod, u = 0, v = 1, t;
while(n != 0) {
t = m / n;
m -= t * n;
u -= t * v;
if (m != 0) {
t = n / m;
n -= t * m;
v -= t * u;
} else {
v %= mod;
if (v < 0) v += mod;
return v;
}
}
u %= mod;
if (u < 0) u += mod;
return u;
} catch (ArrayIndexOutOfBoundsException e) {
throw new IllegalArgumentException();
}
}
public int factorial(int n) {
try {
if (fact.length > n) return fact[n];
long ret = fact[fact.length - 1];
for (int i = fact.length;i <= n;++ i) ret = ret * i % mod;
return (int)ret;
} catch (ArrayIndexOutOfBoundsException e) {
throw new IllegalArgumentException();
}
}
public int permutation(int n, int k) {
if (k < 0) throw new IllegalArgumentException();
if (n < k) return 0;
if (fact.length > n) return (int)((long)fact[n] * invfact[n - k] % mod);
long ret = 1;
for (int i = n - k + 1;i <= n;++ i) ret = ret * i % mod;
return (int)ret;
}
public int combination(int n, int k) {
if (k < 0) throw new IllegalArgumentException();
if (n < k) return 0;
if (fact.length > n) return (int)((long)fact[n] * invfact[k] % mod * invfact[n - k] % mod);
long ret = 1;
if (n < 2 * k) k = n - k;
if (invfact.length > k) ret = invfact[k];
else ret = inverse(factorial(k));
for (int i = n - k + 1;i <= n;++ i) ret = ret * i % mod;
return (int)ret;
}
public int multinomial(int n, int... k) {
int sum = 0;
for (int i : k) sum += i;
long ret = factorial(n);
if (fact.length > n) {
for (int i : k) {
if (i < 0) throw new IllegalArgumentException();
ret = ret * invfact[i] % mod;
sum += i;
}
if (sum > n) return 0;
ret = ret * invfact[n - sum] % mod;
} else {
for (int i : k) {
if (i < 0) throw new IllegalArgumentException();
if (invfact.length > i) ret = ret * invfact[i] % mod;
else ret = ret * inverse(factorial(i)) % mod;
sum += i;
}
if (sum > n) return 0;
if (invfact.length > n - sum) ret = ret * invfact[n - sum] % mod;
else ret = ret * inverse(factorial(n - sum)) % mod;
}
return (int)ret;
}
public int multichoose(int n, int k) {
return combination(mod(n + k - 1), k);
}
public int catalan(int n) {
return divide(combination(mod(2 * n), n), mod(n + 1));
}
public int pow(int n, int m) {
long ans = 1, num = n;
if (m < 0) {
m = -m;
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % mod;
m >>>= 1;
num = num * num % mod;
}
return inverse((int)ans);
}
while (m != 0) {
if ((m & 1) != 0) ans = ans * num % mod;
m >>>= 1;
num = num * num % mod;
}
return (int)ans;
}
public int pow(long n, long m) {
return pow((int)(n % mod), (int)(m % (mod - 1)));
}
public int totient() {
return totient;
}
public boolean isPrime() {
return totient == mod - 1;
}
public int mod(int n) {
return (n %= mod) < 0 ? n + mod : n;
}
public int mod(long n) {
return (int)((n %= mod) < 0 ? n + mod : n);
}
public int add(int n, int m) {
return mod(n + m);
}
public int add(long n, long m) {
return mod(n + m);
}
public int subtract(int n, int m) {
return mod(n - m);
}
public int subtract(long n, long m) {
return mod(n - m);
}
public int multiply(int n, int m) {
int ans = (int)((long)n * m % mod);
return ans < 0 ? ans + mod : ans;
}
public int multiply(long n, long m) {
return multiply(mod(n), mod(m));
}
public int divide(int n, int m) {
return multiply(n, inverse(mod(m)));
}
public int divide(long n, long m) {
return multiply(n, inverse(mod(m)));
}
}
public static class AbstractArray<T> extends AbstractList<T> implements RandomAccess{
private final Object[] array;
public AbstractArray(int size) {
array = new Object[size];
}
public AbstractArray(T[] array) {
this(array.length);
System.arraycopy(array, 0, this.array, 0, array.length);
}
@Override
public T set(int index, T element) {
T ret = get(index);
array[index] = element;
return ret;
}
@Override
public T get(int index) {
@SuppressWarnings("unchecked")
T ret = (T)array[index];
return ret;
}
public Object[] get() {
return array;
}
public T[] get(T[] array) {
if (array.length < this.array.length) {
@SuppressWarnings("unchecked")
T[] ret = (T[])Arrays.copyOfRange(this.array, 0, this.array.length, array.getClass());
return ret;
}
System.arraycopy(this.array, 0, array, 0, this.array.length);
return array;
}
@Override
public int size() {
return array.length;
}
public int length() {
return size();
}
@Override
public int hashCode() {
return Arrays.hashCode(array);
}
private class Iter implements Iterator<T> {
private int index;
private Iter() {
index = 0;
}
@Override
public boolean hasNext() {
return index < array.length;
}
@Override
public T next() {
return get(index++);
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<T> iterator() {
return new Iter();
}
}
public static class Array<T> extends AbstractArray<T> implements Serializable{
private static final long serialVersionUID = 2749604433067098063L;
public Array(int size) {
super(size);
}
public Array(T[] array) {
super(array);
}
public T front() {
return get(0);
}
public T back() {
return get(size() - 1);
}
}
}