VvyLw's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:warning: Java/library/math/ModPrime.java

Depends on

Required by

Code

package library.math;

/**
 * 二項係数の演算を高速で行うクラス
 * modは素数
 * 前計算にO(len + log mod)かかる
 * @see <a href="https://blog.hamayanhamayan.com/entry/2018/06/06/210256">参考元</a>
 */
public final class ModPrime {
	private final int len, mod;
	private final long[] f, rf;
	/**
	 * コンストラクタ
	 * @param mod 素数
	 * @param sz 取りうる値の最大値
	 */
	public ModPrime(final int mod, final int sz) {
		this.mod = mod;
		len = Math.min(sz + 1, mod);
		f = new long[len];
		rf = new long[len];
		init();
	}
	private final long inv(long x) {
		long res = 1, k = mod - 2;
		while(k > 0) {
			if(k % 2 == 1) {
				res = (res * x) % mod;
			}
			x = (x * x) % mod;
			k >>= 1;
		}
		return res;
	}
	private final void init() {
		f[0] = 1;
		for(int i = 0; ++i < len;) {
			f[i] = (f[i - 1] * i) % mod;
		}
		rf[len - 1] = inv(f[len - 1]);
		for(int i = len; --i > 0;) {
			rf[i - 1] = (rf[i] * i) % mod;
		}
	}
	/**
	 * nCkを返す
	 * @param n
	 * @param k
	 * @return 二項係数
	 */
	public final long C(final int n, final int k) {
		if(k < 0 || n < k) {
			return 0;
		}
		final long a = f[n], b = rf[n - k], c = rf[k], bc = (b * c) % mod;
		return (a * bc) % mod;
	}
	/**
	 * nPkを返す
	 * @param n
	 * @param k
	 * @return 順列
	 */
	public final long P(final int n, final int k) {
		if (k < 0 || n < k) {
			return 0;
		}
		final long a = f[n], b = rf[n - k];
		return (a * b) % mod;
	}
	/**
	 * nHkを返す
	 * @param n
	 * @param k
	 * @return 重複順列
	 */
	public final long H(final int n, final int k) {
		if (n == 0 && k == 0) {
			return 1;
		}
		return C(n + k - 1, k);
	}
	/**
	 * n!を返す
	 * @param n
	 * @return 階乗 mod P
	 */
	public final long fact(final int n){ return f[n]; }
}
Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/user_defined.py", line 68, in bundle
    raise RuntimeError('bundler is not specified: {}'.format(str(path)))
RuntimeError: bundler is not specified: Java/library/math/ModPrime.java
Back to top page