結果

問題 No.1039 Project Euler でやれ
ユーザー 37zigen37zigen
提出日時 2020-02-28 19:21:23
言語 Java11
(openjdk 11.0.7)
結果
AC  
実行時間 331 ms / 2,000 ms
コード長 9,276 Byte
コンパイル時間 2,667 ms
使用メモリ 31,844 KB
最終ジャッジ日時 2020-07-13 21:01:02

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 171 ms
29,544 KB
testcase_01 AC 177 ms
29,856 KB
testcase_02 AC 183 ms
30,212 KB
testcase_03 AC 216 ms
31,824 KB
testcase_04 AC 211 ms
31,844 KB
testcase_05 AC 193 ms
31,812 KB
testcase_06 AC 190 ms
30,260 KB
testcase_07 AC 159 ms
29,512 KB
testcase_08 AC 171 ms
29,564 KB
testcase_09 AC 185 ms
30,064 KB
testcase_10 AC 174 ms
29,560 KB
testcase_11 AC 184 ms
30,320 KB
testcase_12 AC 163 ms
29,536 KB
testcase_13 AC 170 ms
29,556 KB
testcase_14 AC 282 ms
29,936 KB
testcase_15 AC 331 ms
30,224 KB
testcase_16 AC 155 ms
29,560 KB
testcase_17 AC 155 ms
29,580 KB
testcase_18 AC 152 ms
29,516 KB
testcase_19 AC 143 ms
29,524 KB
権限があれば一括ダウンロードができます

ソースコード

diff #
import java.util.Arrays;
import java.util.Scanner;

class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		if (!(1 <= M && M < 1e6))
			throw new AssertionError();
		new Main().run(M);
	}

	static long MODULO = (long) 1e9 + 7;

	long pow(long a, long n) {
		n = (n % (MODULO - 1) + (MODULO - 1)) % (MODULO - 1);
		long ret = 1;
		for (; n > 0; n >>= 1, a = a * a % MODULO)
			if (n % 2 == 1)
				ret = ret * a % MODULO;
		return ret;
	}

	long inv(long a) {
		return pow(a, MODULO - 2);
	}

	long solve(long p, int e) {
		long[][][] dp = new long[e + 1][e + 2][e + 1];
		dp[0][e + 1][0] = 1;
		for (int sumKU = 0; sumKU < e; ++sumKU) {
			for (int k = e + 1; k >= 1; --k) {
				for (int sumU = 0; sumU < e; ++sumU) {
					if (dp[sumKU][k][sumU] == 0)
						continue;
					for (int nk = k - 1; nk >= 1; --nk) {
						for (int nu = 1; sumKU + nk * nu <= e; ++nu) {
							// (Z/p^nk)^nu
							long add = pow(p, nk * nu * sumU);
							for (int m = 0; m < nu; ++m) {
								add *= (pow(p, nk * nu) - pow(p, nu * (nk - 1) + m)) % MODULO * pow(p, nk * sumU)
										% MODULO;
								add %= MODULO;
							}
							dp[sumKU + nk * nu][nk][sumU + nu] += inv(add) * dp[sumKU][k][sumU] % MODULO;
							dp[sumKU + nk * nu][nk][sumU + nu] %= MODULO;
						}
					}
				}
			}
		}
		long ret = 0;
		for (int i = 1; i <= e; ++i)
			for (int j = 1; j <= e; ++j)
				ret = (ret + dp[e][i][j]) % MODULO;
		ret = (ret % MODULO + MODULO) % MODULO;
		return ret;
	}

	void run(int M) {
		long fac = factorial(M);
		long ans = 1;
		for (long div = 2; div <= M; ++div) {
			int e = 0;
			while (M % div == 0) {
				M /= div;
				++e;
			}
			if (e > 0)
				ans = ans * solve(div, e) % MODULO;
		}
		ans = ans * fac % MODULO;
		System.out.println(ans);
	}

	// return F^n(0)
	long factorial(long N) {
		build(MODULO);
		long v = (long) Math.sqrt(N);
		int m = 0;
		long[][][] f = new long[m + 1][][];
		for (int i = 0; i <= m; ++i) {
			f[i] = F(m, i * v, N);
		}
		for (int bit = 63; bit >= 0; --bit) {
			if (m > 0) { // m -> 2m
				long[][][] fs = Arrays.copyOfRange(matshift(f, v, m * inv(v, MODULO) % MODULO), m + 1, 2 * m + 2);
				f = matshift(f, v, f.length); // length: m + 1 -> 2m + 2
				fs = matshift(fs, v, fs.length); // length: m + 1 -> 2m + 2
				m *= 2;
				long[][][] f2 = new long[m + 1][][];
				for (int i = 0; i <= m; ++i) {
					f2[i] = matmul(fs[i], f[i]);
				}
				f = f2;
			}
			if (((1L << bit) & v) > 0) { // m -> m + 1
				++m;
				long[][][] f2 = new long[m + 1][][];
				for (int i = 0; i < m; ++i) {
					f2[i] = matmul(f(m, v * i, N), f[i]);
				}
				f2[m] = F(m, m * v, N);
				f = f2;
			}
		}

		long[][] ret = new long[][] { { 1, 0 }, { 0, 1 } };
		for (int i = 0; i <= v - 1; ++i) {
			ret = matmul(f[i], ret);
		}
		for (long i = v * v + 1; i <= N; ++i) {
			ret = matmul(f(i, 0, N), ret);
		}
		return ret[0][0];
	}

	long[][] f(long k, long x, long N) {
		long[][] ret = new long[][] { { x + k, 0 }, { 0, 0 } };
		return ret;
	}

	long[][] F(long n, long x, long N) {
		long[][] ret = new long[][] { { 1, 0 }, { 0, 1 } };
		for (int i = 1; i <= n; ++i) {
			ret = matmul(f(i, x, N), ret);
		}
		return ret;
	}

	// m : degree of polynomial
	//
	// Converting
	// from
	// f[0], f[v] , f[2v] , ..., f[mv]
	// to
	// f[0], f[v] , f[2v] , ..., f[mv], f[shift*v], f[shift*v + v] ,f[shift*v + mv]
	// .
	//
	// See f as f(x) = f[x*v].

	long[][][] matshift(long[][][] h, long v, long shift) {
		long[] a0 = new long[h.length];
		for (int i = 0; i < h.length; ++i) {
			a0[i] = h[i][0][0];
		}
		a0 = shift(a0, v, shift);
		long[][][] ret = new long[a0.length][2][2];
		for (int i = 0; i < ret.length; ++i) {
			ret[i] = new long[][] { { a0[i], 0 }, { 0, 0 } };
		}
		return ret;
	}

	long[] shift(long[] h, long v, long shift) {
		int degree = h.length - 1;
		long[] a = new long[degree + 1];
		long[] b = new long[2 * degree + 1];
		long[] ret = new long[2 * h.length];
		for (int i = 0; i < h.length; ++i) {
			ret[i] = h[i];
		}

		long prd = 1;
		for (int i = 0; i <= degree; ++i) {
			a[i] = h[i] * ifac[i] % MODULO * ifac[degree - i] % MODULO * ((degree - i) % 2 == 0 ? 1 : -1);
			if (a[i] < 0)
				a[i] += MODULO;
		}
		for (int i = 0; i <= 2 * degree; ++i)
			b[i] = inv(shift - degree + i, MODULO);
		long[] c = middle_product(a, b, MODULO);
		for (int i = 0; i <= degree; ++i) {
			prd = prd * (shift - i == 0 ? 1 : (shift - i)) % MODULO;
			if (prd < 0)
				prd += MODULO;
		}
		for (int i = 0; i < h.length; ++i) {
			ret[i + h.length] = prd * c[i] % MODULO;
			prd = prd * (shift + i + 1) % MODULO * inv(shift + i - degree, MODULO) % MODULO;
			if (prd < 0)
				prd += MODULO;
		}
		if (0 <= shift && shift <= degree) {
			for (int i = 0; i + shift < h.length; ++i) {
				ret[i + h.length] = h[i + (int) shift];
			}
		}
		return ret;
	}

	long[][] matmul(long[][] a, long[][] b) {
		long[][] ret = new long[a.length][b[0].length];
		for (int i = 0; i < a.length; ++i) {
			for (int j = 0; j < b[i].length; ++j) {
				for (int k = 0; k < a[i].length; ++k) {
					ret[i][j] += a[i][k] * b[k][j] % MODULO;
					if (ret[i][j] >= MODULO)
						ret[i][j] -= MODULO;
				}
			}
		}
		return ret;
	}

	// inv[0] := 1
	long inv(long a, long mod) {
		a %= mod;
		if (a < 0)
			a += mod;
		if (a == 0) {
			throw new AssertionError();
			// return 1;
		}
		long b = mod;
		long p = 1, q = 0;
		while (b > 0) {
			long c = a / b;
			long d;
			d = a;
			a = b;
			b = d % b;
			d = p;
			p = q;
			q = d - c * q;
		}
		long ret = p < 0 ? (p + mod) : p;
		return ret;
	}

	final int MAX = 112345;
	long[] fac = new long[MAX];
	long[] ifac = new long[MAX];
	long[] inv = new long[MAX];

	void build(long MOD) {
		fac[0] = ifac[0] = inv[0] = fac[1] = ifac[1] = inv[1] = 1;
		for (int i = 2; i < fac.length; ++i) {
			fac[i] = fac[i - 1] * i % MOD;
			inv[i] = MOD - inv[(int) (MOD % i)] * (MOD / i) % MOD;
			ifac[i] = inv[i] * ifac[i - 1] % MOD;
		}
	}

	long[] middle_product(long[] a, long[] b, long mod0) {
		long[] MOD = new long[] { 1012924417, 1224736769, 1007681537 };
		long[] gen = new long[] { 5, 3, 3 };
		long[][] c = new long[3][];
		for (int i = 0; i < 3; ++i) {
			c[i] = middle_product_(Arrays.copyOf(a, a.length), Arrays.copyOf(b, b.length), MOD[i], gen[i]);
		}
		for (int i = 0; i < c[0].length; ++i) {
			c[0][i] = garner(new long[] { c[0][i], c[1][i], c[2][i] }, MOD, mod0);
		}
		return c[0];
	}

	// a : d 次
	// b : 2d + 1 次
	long[] middle_product_(long[] a, long[] b, long mod, long gen) {
		int degree = a.length - 1;
		{
			int s = 0;
			int t = degree;
			while (s < t) {
				a[s] ^= a[t];
				a[t] ^= a[s];
				a[s] ^= a[t];
				s++;
				t--;
			}
		}
		int level = Long.numberOfTrailingZeros(mod - 1);
		long root = gen;
		long omega = pow(root, (mod - 1) >> level, mod);
		int n = Integer.highestOneBit(2 * degree) << 1;
		long[] roots = new long[level];
		long[] iroots = new long[level];
		roots[0] = omega;
		iroots[0] = inv(omega, mod);
		for (int i = 1; i < level; ++i) {
			roots[i] = roots[i - 1] * roots[i - 1] % mod;
			iroots[i] = iroots[i - 1] * iroots[i - 1] % mod;
		}
		a = Arrays.copyOf(a, n);
		b = Arrays.copyOf(b, n);
		a = fft(a, true, mod, roots, iroots);
		b = fft(b, false, mod, roots, iroots);
		for (int i = 0; i < n; ++i)
			a[i] = a[i] * b[i] % mod;
		a = fft(a, true, mod, roots, iroots);
		long inv = inv(n, mod);
		for (int i = 0; i < n; ++i) {
			a[i] = a[i] * inv % mod;
		}
		return a;
	}

	long[] fft(long[] a, boolean inv, long mod, long[] roots, long[] iroots) {
		int n = a.length;

		int c = 0;
		for (int i = 1; i < n; ++i) {
			for (int j = n >> 1; j > (c ^= j); j >>= 1)
				;
			if (c > i) {
				long d = a[i];
				a[i] = a[c];
				a[c] = d;
			}
		}
		int level = Long.numberOfTrailingZeros(mod - 1);
		for (int i = 1; i < n; i *= 2) {
			long w;
			if (!inv)
				w = roots[level - Integer.numberOfTrailingZeros(i) - 1];
			else
				w = iroots[level - Integer.numberOfTrailingZeros(i) - 1];
			for (int j = 0; j < n; j += 2 * i) {
				long wn = 1;
				for (int k = 0; k < i; ++k) {
					long u = a[j + k];
					long v = a[j + k + i] * wn % mod;
					a[j + k] = u + v;
					a[j + k + i] = u - v;
					if (a[j + k] >= mod)
						a[j + k] -= mod;
					if (a[j + k + i] < 0)
						a[j + k + i] += mod;
					wn = wn * w % mod;
				}
			}
		}
		return a;
	}

	long pow(long a, long n, long mod) {
		long ret = 1;
		for (; n > 0; n >>= 1, a = a * a % mod) {
			if (n % 2 == 1)
				ret = ret * a % mod;
		}
		return ret;
	}

	long garner(long[] x, long[] mod, long mod0) {
		assert x.length == mod.length;
		int n = x.length;
		long[] gamma = new long[n];
		for (int i = 0; i < n; i++) {
			long prod = 1;
			for (int j = 0; j < i; j++) {
				prod = prod * mod[j] % mod[i];
			}
			gamma[i] = inv(prod, mod[i]);
		}
		long[] v = new long[n];
		v[0] = x[0];
		for (int i = 1; i < n; i++) {
			long tmp = v[i - 1];
			for (int j = i - 2; j >= 0; j--) {
				tmp = (tmp * mod[j] + v[j]) % mod[i];
			}
			v[i] = (x[i] - tmp) * gamma[i] % mod[i];
			while (v[i] < 0)
				v[i] += mod[i];
		}
		long ret = 0;
		for (int i = v.length - 1; i >= 0; i--) {
			ret = (ret * mod[i] + v[i]) % mod0;
		}
		return ret;
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}
0