結果
| 問題 | No.940 ワープ ε=ε=ε=ε=ε=│;p>д＜│ |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2019-11-26 17:50:15 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 35,762 bytes |
| コンパイル時間 | 6,086 ms |
| コンパイル使用メモリ | 105,632 KB |
| 実行使用メモリ | 66,008 KB |
| 最終ジャッジ日時 | 2023-08-18 22:53:16 |
| 合計ジャッジ時間 | 18,136 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 122 ms
56,372 KB |
| testcase_01 | AC | 124 ms
55,972 KB |
| testcase_02 | AC | 128 ms
55,864 KB |
| testcase_03 | AC | 1,140 ms
59,868 KB |
| testcase_04 | WA | - |
| testcase_05 | AC | 288 ms
60,052 KB |
| testcase_06 | AC | 200 ms
59,936 KB |
| testcase_07 | AC | 209 ms
60,008 KB |
| testcase_08 | AC | 194 ms
59,760 KB |
| testcase_09 | AC | 270 ms
59,704 KB |
| testcase_10 | AC | 214 ms
60,032 KB |
| testcase_11 | AC | 188 ms
60,028 KB |
| testcase_12 | AC | 316 ms
57,868 KB |
| testcase_13 | AC | 271 ms
59,968 KB |
| testcase_14 | AC | 154 ms
58,212 KB |
| testcase_15 | TLE | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
ソースコード
package yukicoder_3679;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.Set;
import java.util.function.BinaryOperator;
public class Main {
public static void main(String[] args) {
new Main();
}
public Main() {
try (Scanner sc = new Scanner(System.in)) {
// ごめんなさい、解けないのでとりあえず愚直を投げます
// まだ考えてみます(包除原理っぽい……？)
int X = sc.nextInt(), Y = sc.nextInt(), Z = sc.nextInt();
ModUtility mod = new ModUtility(new Prime(1000000007), 2 * (X + Y + Z));
ModInteger[] dp = new ModInteger[X + Y + Z];
for (int i = 0;i < dp.length;++ i) {
dp[i] = mod.create(mod.multichoose(X + 1, i));
dp[i].multiplyEqual(mod.multichoose(Y + 1, i));
dp[i].multiplyEqual(mod.multichoose(Z + 1, i));
for (int j = 1;j <= i;++ j) dp[i].subtractEqual(dp[i - j].multiply(mod.combination(i + 1, j)));
}
ModInteger ans = mod.create();
for (ModInteger i : dp) ans.addEqual(i);
System.out.println(ans);
}
}
/*
* ここから下、ライブラリ
*/
/**
* 演算が結合法則を満たすことを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
*/
public interface Associative<T> extends BinaryOperator<T>{
/**
* repeat個のelementを順次演算した値を返します。
* @param element 演算する値
* @param repeat 繰り返す回数、1以上であること
* @return 演算を+として、element + element + ... + elementと演算をrepeat-1回行った値
*/
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;
}
}
/**
* この演算が逆元を持つことを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
*/
public interface Inverse<T> extends BinaryOperator<T>{
public T inverse(T element);
}
/**
* 演算が交換法則を満たすことを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
*/
public interface Commutative<T> extends BinaryOperator<T>{
}
/**
* 演算が単位元を持つことを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
*/
public interface Identity<T> extends BinaryOperator<T>{
/**
* 単位元を返します。
* @return 単位元
*/
public T identity();
}
/**
* 演算が群であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
*/
public interface Group<T> extends Monoid<T>, Inverse<T>{
/**
* repeat個のelementを順次演算した値を返します。
* @param element 演算する値
* @param repeat 繰り返す回数
* @return 演算を+として、element + element + ... + elementと演算をrepeat-1回行った値
*/
@Override
public default T hyper(T element, int repeat) {
T ret = identity();
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;
}
}
/**
* 演算がモノイドであることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
*/
public interface Monoid<T> extends Associative<T>, Identity<T> {
/**
* repeat個のelementを順次演算した値を返します。
* @param element 演算する値
* @param repeat 繰り返す回数、0以上であること
* @return 演算を+として、element + element + ... + elementと演算をrepeat-1回行った値
*/
@Override
public default T hyper(T element, int repeat) {
if (repeat < 0) throw new IllegalArgumentException("undefined operation");
T ret = identity();
for (T mul = element;repeat > 0;repeat >>= 1, mul = apply(mul, mul)) if ((repeat & 1) != 0) ret = apply(ret, mul);
return ret;
}
}
/**
* 演算が可換モノイドであることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
*/
public interface CommutativeMonoid<T> extends Monoid<T>, Commutative<T> {
}
/**
* 演算がアーベル群(可換群)であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
*/
public interface Abelian<T> extends Group<T>, CommutativeMonoid<T> {
}
/**
* 演算が半環であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface Semiring<T, A extends CommutativeMonoid<T>, M extends Monoid<T>> {
public A getAddition();
public M getMultiplication();
public default T add(T left, T right) {
return getAddition().apply(left, right);
}
public default T multiply(T left, T right) {
return getMultiplication().apply(left, right);
}
public default T additiveIdentity() {
return getAddition().identity();
}
public default T multipleIdentity() {
return getMultiplication().identity();
}
public default int characteristic() {
return 0;
}
}
/**
* 演算が環であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface Ring<T, A extends Abelian<T>, M extends Monoid<T>> extends Semiring<T, A, M>{
}
/**
* 演算が可換環に属することを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface CommutativeRing<T, A extends Abelian<T>, M extends CommutativeMonoid<T>> extends Ring<T, A, M>{
}
/**
* 演算が整域であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface IntegralDomain<T, A extends Abelian<T>, M extends CommutativeMonoid<T>> extends CommutativeRing<T, A, M>{
public boolean isDivisible(T left, T right);
public T divide(T left, T right);
}
/**
* 演算が整閉整域であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface IntegrallyClosedDomain<T, A extends Abelian<T>, M extends CommutativeMonoid<T>> extends IntegralDomain<T, A, M>{
}
/**
* 演算がGCD整域であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface GCDDomain<T, A extends Abelian<T>, M extends CommutativeMonoid<T>> extends IntegrallyClosedDomain<T, A, M>{
public T gcd(T left, T right);
public T lcm(T left, T right);
}
/**
* 素元を提供します。
* @author 31536000
*
* @param <T> 演算の型
*/
public static class PrimeElement<T> {
public final T element;
public PrimeElement(T element) {
this.element = element;
}
}
public interface MultiSet<E> extends Collection<E>{
public int add(E element, int occurrences);
public int count(Object element);
public Set<E> elementSet();
public boolean remove(Object element, int occurrences);
public int setCount(E element, int count);
public boolean setCount(E element, int oldCount, int newCount);
}
/**
* 演算が一意分解整域であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface UniqueFactorizationDomain<T, A extends Abelian<T>, M extends CommutativeMonoid<T>> extends GCDDomain<T, A, M>{
public MultiSet<PrimeElement<T>> PrimeFactorization(T x);
}
/**
* 演算が主イデアル整域であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface PrincipalIdealDomain<T, A extends Abelian<T>, M extends CommutativeMonoid<T>> extends UniqueFactorizationDomain<T, A, M> {
}
/**
* 演算がユークリッド整域であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface EuclideanDomain<T, A extends Abelian<T>, M extends CommutativeMonoid<T>> extends PrincipalIdealDomain<T, A, M>{
public T reminder(T left, T right);
}
/**
* 演算が体であることを示すために使用するマーカー・インターフェースです。
* @author 31536000
*
* @param <T> 二項演算の型
* @param <A> 和に関する演算
* @param <M> 積に関する演算
*/
public interface Field<T, A extends Abelian<T>, M extends Abelian<T>> extends EuclideanDomain<T, A, M>{
@Override
public default boolean isDivisible(T left, T right) {
return !right.equals(additiveIdentity());
}
@Override
public default T divide(T left, T right) {
if (isDivisible(left, right)) throw new ArithmeticException("divide by Additive Identify");
return multiply(left, getMultiplication().inverse(right));
}
@Override
public default T reminder(T left, T right) {
if (isDivisible(left, right)) throw new ArithmeticException("divide by Additive Identify");
return additiveIdentity();
}
@Override
public default T gcd(T left, T right) {
return multipleIdentity();
}
@Override
public default T lcm(T left, T right) {
return multipleIdentity();
}
@Override
public default MultiSet<PrimeElement<T>> PrimeFactorization(T x) {
HashMultiSet<PrimeElement<T>> ret = HashMultiSet.create(1);
ret.add(new PrimeElement<T>(x));
return ret;
}
}
public static class HashMultiSet<E> implements MultiSet<E>, Serializable{
private static final long serialVersionUID = -8378919645386251159L;
private final transient HashMap<E, Integer> map;
private transient int size;
private HashMultiSet() {
map = new HashMap<>();
size = 0;
}
private HashMultiSet(int distinctElements) {
map = new HashMap<>(distinctElements);
size = 0;
}
public static <E> HashMultiSet<E> create() {
return new HashMultiSet<>();
}
public static <E> HashMultiSet<E> create(int distinctElements) {
return new HashMultiSet<>(distinctElements);
}
public static <E> HashMultiSet<E> create(Iterable<? extends E> elements) {
HashMultiSet<E> ret = new HashMultiSet<>();
for (E i : elements) ret.map.compute(i, (v, e) -> e == null ? 1 : ++e);
return ret;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object o) {
return map.containsKey(o);
}
private class Iter implements Iterator<E> {
private final Iterator<Entry<E, Integer>> iter = map.entrySet().iterator();
private E value;
private int count = 0;
@Override
public boolean hasNext() {
if (count > 0) return true;
if (iter.hasNext()) {
Entry<E, Integer> entry = iter.next();
value = entry.getKey();
count = entry.getValue();
return true;
}
return false;
}
@Override
public E next() {
-- count;
return value;
}
}
@Override
public Iterator<E> iterator() {
return new Iter();
}
@Override
public Object[] toArray() {
Object[] ret = new Object[size];
int read = 0;
for (Entry<E, Integer> i : map.entrySet()) Arrays.fill(ret, read, read += i.getValue(), i.getKey());
return ret;
}
@Override
public <T> T[] toArray(T[] a) {
Object[] src = toArray();
if (a.length < src.length) {
@SuppressWarnings("unchecked")
T[] ret = (T[])Arrays.copyOfRange(src, 0, src.length, a.getClass());
return ret;
}
System.arraycopy(src, 0, a, 0, src.length);
return a;
}
@Override
public boolean add(E e) {
add(e, 1);
return true;
}
@Override
public boolean remove(Object o) {
return remove(o, 1);
}
@Override
public boolean containsAll(Collection<?> c) {
boolean ret = true;
for (Object i : c) ret |= contains(i);
return ret;
}
@Override
public boolean addAll(Collection<? extends E> c) {
boolean ret = false;
for (E i : c) ret |= add(i);
return ret;
}
@Override
public boolean removeAll(Collection<?> c) {
boolean ret = false;
for (Object i : c) ret |= remove(i);
return ret;
}
@Override
public boolean retainAll(Collection<?> c) {
return removeAll(c);
}
@Override
public void clear() {
map.clear();
size = 0;
}
@Override
public int add(E element, int occurrences) {
size += occurrences;
return map.compute(element, (k, v) -> v == null ? occurrences : v + occurrences) - occurrences;
}
@Override
public int count(Object element) {
return map.getOrDefault(element, 0);
}
@Override
public Set<E> elementSet() {
return map.keySet();
}
public Set<Entry<E, Integer>> entrySet() {
return map.entrySet();
}
@Override
public boolean remove(Object element, int occurrences) {
try {
@SuppressWarnings("unchecked")
E put = (E) element;
return map.compute(put, (k, v) -> {
if (v == null) return null;
if (v < occurrences) {
size -= v;
return null;
}
size -= occurrences;
return v - occurrences;
}) != null;
} catch (ClassCastException E) {
return false;
}
}
@Override
public int setCount(E element, int count) {
Integer ret = map.put(element, count);
int ret2 = ret == null ? 0 : ret;
size += count - ret2;
return ret2;
}
@Override
public boolean setCount(E element, int oldCount, int newCount) {
boolean ret = map.replace(element, oldCount, newCount);
if (ret) size += newCount - oldCount;
return ret;
}
}
public static class ModInteger extends Number implements Field<ModInteger, Abelian<ModInteger>, Abelian<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 identity() {
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 identity() {
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));
}
}
@Override
public int characteristic() {
return mod;
}
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;
}
protected ModInteger getNewInstance(ModInteger mod) {
return new ModInteger(mod);
}
public ModInteger add(int n) {
return getNewInstance(this).addEqual(n);
}
public ModInteger add(long n) {
return getNewInstance(this).addEqual(n);
}
public ModInteger add(ModInteger n) {
return getNewInstance(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 getNewInstance(this).subtractEqual(n);
}
public ModInteger subtract(long n) {
return getNewInstance(this).subtractEqual(n);
}
public ModInteger subtract(ModInteger n) {
return getNewInstance(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 getNewInstance(this).multiplyEqual(n);
}
public ModInteger multiply(long n) {
return getNewInstance(this).multiplyEqual(n);
}
public ModInteger multiply(ModInteger n) {
return getNewInstance(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 getNewInstance(this).divideEqual(n);
}
public ModInteger divide(long n) {
return getNewInstance(this).divideEqual(n);
}
public ModInteger divide(ModInteger n) {
return getNewInstance(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 getNewInstance(this).powEqual(n);
}
public ModInteger pow(long n) {
return getNewInstance(this).powEqual(n);
}
public ModInteger pow(ModInteger n) {
return getNewInstance(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;
}
}
/**
* 素数を法とする演算上で、組み合わせの計算を高速に行います。
* @author 31536000
*
*/
public static class ModUtility {
private final int mod;
private int[] fact, inv, invfact;
/**
* modを法として、演算を行います。
* @param mod 法とする素数
*/
public ModUtility(Prime mod) {
this(mod, 2);
}
/**
* modを法として、演算を行います。
* @param mod 法とする素数
* @param calc 予め前計算しておく大きさ
*/
public ModUtility(Prime mod, int calc) {
this.mod = mod.prime;
precalc(calc);
}
/**
* calcの大きさだけ、前計算を行います。
* @param calc 前計算をする大きさ
*/
public void precalc(int calc) {
++ 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);
}
}
/**
* modを法とする剰余環上で振舞う整数を返します。
* @return modを法とする整数、初期値は0
*/
public ModInteger create() {
return new ModInt();
}
/**
* modを法とする剰余環上で振舞う整数を返します。
* @param n 初期値
* @return modを法とする整数
*/
public ModInteger create(int n) {
return new ModInt(n);
}
private class ModInt extends ModInteger {
private static final long serialVersionUID = -2435281861935422575L;
public ModInt() {
super(mod);
}
public ModInt(int n) {
super(mod, n);
}
public ModInt(ModInteger mod) {
super(mod);
}
@Override
protected ModInteger getNewInstance(ModInteger mod) {
return new ModInt(mod);
}
@Override
protected int inverse(int n) {
return ModUtility.this.inverse(n);
}
}
/**
* modを法として、nの逆元を返します。<br>
* 計算量はO(log n)です。
* @param n 逆元を求めたい値
* @return 逆元
*/
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();
}
}
/**
* n!を、modを法として求めた値を返します。<br>
* 計算量はO(n)です。
* @param n 階乗を求めたい値
* @return nの階乗をmodで割った余り
*/
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();
}
}
/**
* nPkをmodで割った余りを求めます。<br>
* 計算量はO(n-k)です。
* @param n 左辺
* @param k 右辺
* @return nPkをmodで割った余り
*/
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;
}
/**
* nCkをmodで割った余りを求めます。<br>
* 計算量はO(n-k)です。
* @param n 左辺
* @param k 右辺
* @return nCkをmodで割った余り
*/
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;
}
/**
* 他項係数をmodで割った余りを求めます。<br>]
* 計算量はO(n)です。
* @param n 左辺
* @param k 右辺、合計がn以下である必要がある
* @return 他項係数
*/
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;
}
/**
* n個からk個を選ぶ重複組み合わせnHkをmodで割った余りを求めます。<br>
* 計算量はO(min(n, k))です。
* @param n 左辺
* @param k 右辺
* @return nHkをmodで割った余り
*/
public int multichoose(int n, int k) {
return combination(mod(n + k - 1), k);
}
/**
* カタラン数C(n)をmodで割った余りを求めます。<br>
* 計算量はO(n)です。
* @param n 求めたいカタラン数の番号
* @return カタラン数
*/
public int catalan(int n) {
return divide(combination(mod(2 * n), n), mod(n + 1));
}
/**
* nのm乗をmodで割った余りを求めます。<br>
* 計算量はO(log m)です。
* @param n 床
* @param m 冪指数
* @return n^mをmodで割った余り
*/
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;
}
/**
* nのm乗をmodで割った余りを求めます。<br>
* 計算量はO(log m)です。
* @param n 床
* @param m 冪指数
* @return n^mをmodで割った余り
*/
public int pow(long n, long m) {
return pow((int)(n % mod), (int)(n % (mod - 1)));
}
/**
* 現在のmod値のトーシェント数を返します。<br>
* なお、これはmod-1に等しいです。
* @return トーシェント数
*/
public int totient() {
return mod - 1;
}
/**
* nのトーシェント数を返します。<br>
* 計算量はO(sqrt n)です。
* @param n トーシェント数を求めたい値
* @return nのトーシェント数
*/
public static int totient(int n) {
int totient = n;
for (int i = 2;i * i <= n;++ i) {
if (n % i == 0) {
totient = totient / i * (i - 1);
while ((n %= i) % i == 0);
}
}
if (n != 1) totient = totient / n * (n - 1);
return totient;
}
/**
* nをmodで割った余りを返します。
* @param n 演算する値
* @return nをmodで割った余り
*/
public int mod(int n) {
return (n %= mod) < 0 ? n + mod : n;
}
/**
* nをmodで割った余りを返します。
* @param n 演算する値
* @return nをmodで割った余り
*/
public int mod(long n) {
return (int)((n %= mod) < 0 ? n + mod : n);
}
/**
* n+mをmodで割った余りを返します。
* @param n 足される値
* @param m 足す値
* @return n+mをmodで割った余り
*/
public int add(int n, int m) {
return mod(n + m);
}
/**
* n-mをmodで割った余りを返します。
* @param n 引かれる値
* @param m 引く値
* @return n-mをmodで割った余り
*/
public int subtract(int n, int m) {
return mod(n - m);
}
/**
* n*mをmodで割った余りを返します。
* @param n 掛けられる値
* @param m 掛ける値
* @return n*mをmodで割った余り
*/
public int multiply(int n, int m) {
int ans = (int)((long)n * m % mod);
return ans < 0 ? ans + mod : ans;
}
/**
* n/mをmodで割った余りを返します。
* @param n 割られる値
* @param m 割る値
* @return n/mをmodで割った余り
*/
public int divide(int n, int m) {
return multiply(n, inverse(m));
}
/**
* fを通ることが分かっているfの要素数-1次の関数について、xの位置における値をmodで割った余りを返します。<br>
* 計算量はO(f)です。
* @param f 関数の形
* @param x 求める位置
* @return 求めたい値をmodで割った余り
*/
public ModInteger lagrangePolynomial(ModInteger[] f, int x) {
if (f.length > x) return f[x];
if (x > fact.length) precalc(x);
ModInteger ret = create(0);
ModInteger[] dp = new ModInteger[f.length], dp2 = new ModInteger[f.length];
dp[0] = create(1);
dp2[f.length - 1] = create(1);
for (int i = 1;i < f.length;++ i) {
dp[i] = dp[i - 1].multiply(x - i - 1);
dp2[f.length - i - 1] = dp2[f.length - i].multiply(x - f.length + i);
}
for (int i = 0;i < f.length;++ i) {
ModInteger tmp = f[i].multiply(dp[i]).multiplyEqual(dp2[i]).multiplyEqual(inv[i]).multiplyEqual(inv[f.length - 1 - i]);
if ((f.length - i & 1) == 0) ret.addEqual(tmp);
else ret.subtractEqual(tmp);
}
return ret;
}
}
/**
* 素数を渡すためのクラスです。<br>
* 中身が確実に素数であることを保証するときに使ってください。
*
* @author 31536000
*
*/
public static class Prime extends Number{
private static final long serialVersionUID = 8216169308184181643L;
public final int prime;
/**
* 素数を設定します。
*
* @param prime 素数
* @throws IllegalArgumentException 素数以外を渡した時
*/
public Prime(int prime) {
if (!isPrime(prime)) throw new IllegalArgumentException(prime + " is not prime");
this.prime = prime;
}
private static final int bases[] = {15591, 2018, 166, 7429, 8064, 16045, 10503, 4399, 1949, 1295, 2776, 3620, 560, 3128, 5212, 2657, 2300, 2021, 4652, 1471, 9336, 4018, 2398, 20462, 10277, 8028, 2213, 6219, 620, 3763, 4852, 5012, 3185, 1333, 6227, 5298, 1074, 2391, 5113, 7061, 803, 1269, 3875, 422, 751, 580, 4729, 10239, 746, 2951, 556, 2206, 3778, 481, 1522, 3476, 481, 2487, 3266, 5633, 488, 3373, 6441, 3344, 17, 15105, 1490, 4154, 2036, 1882, 1813, 467, 3307, 14042, 6371, 658, 1005, 903, 737, 1887, 7447, 1888, 2848, 1784, 7559, 3400, 951, 13969, 4304, 177, 41, 19875, 3110, 13221, 8726, 571, 7043, 6943, 1199, 352, 6435, 165, 1169, 3315, 978, 233, 3003, 2562, 2994, 10587, 10030, 2377, 1902, 5354, 4447, 1555, 263, 27027, 2283, 305, 669, 1912, 601, 6186, 429, 1930, 14873, 1784, 1661, 524, 3577, 236, 2360, 6146, 2850, 55637, 1753, 4178, 8466, 222, 2579, 2743, 2031, 2226, 2276, 374, 2132, 813, 23788, 1610, 4422, 5159, 1725, 3597, 3366, 14336, 579, 165, 1375, 10018, 12616, 9816, 1371, 536, 1867, 10864, 857, 2206, 5788, 434, 8085, 17618, 727, 3639, 1595, 4944, 2129, 2029, 8195, 8344, 6232, 9183, 8126, 1870, 3296, 7455, 8947, 25017, 541, 19115, 368, 566, 5674, 411, 522, 1027, 8215, 2050, 6544, 10049, 614, 774, 2333, 3007, 35201, 4706, 1152, 1785, 1028, 1540, 3743, 493, 4474, 2521, 26845, 8354, 864, 18915, 5465, 2447, 42, 4511, 1660, 166, 1249, 6259, 2553, 304, 272, 7286, 73, 6554, 899, 2816, 5197, 13330, 7054, 2818, 3199, 811, 922, 350, 7514, 4452, 3449, 2663, 4708, 418, 1621, 1171, 3471, 88, 11345, 412, 1559, 194};
private static boolean isSPRP(int n, int a) {
int d = n - 1, s = 0;
while ((d & 1) == 0) {
++s;
d >>= 1;
}
long cur = 1, pw = d;
while (pw != 0) {
if ((pw & 1) != 0) cur = (cur * a) % n;
a = (int)(((long)a * a) % n);
pw >>= 1;
}
if (cur == 1) return true;
for (int r = 0; r < s; r++ ) {
if (cur == n - 1) return true;
cur = (cur * cur) % n;
}
return false;
}
/**
* 与えられた値が素数か否かを判定します。<br>
* この実装はhttp://ceur-ws.org/Vol-1326/020-Forisek.pdfに基づきます。
* @param x 判定したい値
* @return xが素数ならtrue
*/
public static boolean isPrime(int x) {
if (x == 2 || x == 3 || x == 5 || x == 7) return true;
if ((x & 1) == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return false;
if (x < 121) return x > 1;
long h = x;
h = ((h >> 16) ^ h) * 0x45d9f3b;
h = ((h >> 16) ^ h) * 0x45d9f3b;
h = ((h >> 16) ^ h) & 0xFF;
return isSPRP(x, bases[(int)h]);
}
@Override
public int intValue() {
return prime;
}
@Override
public long longValue() {
return prime;
}
@Override
public float floatValue() {
return prime;
}
@Override
public double doubleValue() {
return prime;
}
@Override
public String toString() {
return String.valueOf(prime);
}
}
}