結果
| 問題 |
No.1039 Project Euler でやれ
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2020-02-28 18:58:36 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 262 ms / 2,000 ms |
| コード長 | 9,061 bytes |
| コンパイル時間 | 2,707 ms |
| コンパイル使用メモリ | 93,168 KB |
| 実行使用メモリ | 47,912 KB |
| 最終ジャッジ日時 | 2024-11-08 02:57:54 |
| 合計ジャッジ時間 | 8,009 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 18 |
ソースコード
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();
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} };
if (ret[0][1] >= MODULO)
ret[0][1] -= MODULO;
if (ret[1][1] >= MODULO)
ret[1][1] -= MODULO;
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));
}
}