Submission #24538

---

Source Code Expand

module main;

import std.stdio;
import std.conv;
import std.range;
import std.string;
const mod = 10_0000_0007;

void main()
{
    auto buf = readln().strip().split();
    int n = buf[0].to!int();
    if (n < 0)
    {
        n = -n;
    }
    int m = buf[1].to!int();
    int[int] power; // nの素因数 p の指数 e (> 0)
    foreach (prime; known_primes())
    {
        while (n % prime == 0)
        {
            power[prime] += 1;
            n /= prime;
        }
    }
    // (いま) n = 1 なら (もとの) n の素因数は小さいものばかり。
    // そうでない場合は大きい素因数だけの積になっているが、それは単一の素数にほかならない。
    if (1 < n)
    {
        power[n] += 1;
    }
    // 符号の処理: 最後以外は自由に選べる。
    ulong ret = 1;
    foreach (i; 1..m)
    {
        ret *= 2;
        ret %= mod;
    }
    // メイン。素因数ごとに指数を割り振る。
    foreach (p, e; power)
    {
        ret *= partition(e, m);
        ret %= mod;
    }
    writefln("%d", ret);
}

/// '既知' の素数リスト: 今回は入力が 10^9 以下なので, 10^(9/2) までの素数を求めておけばよい。
int[] known_primes()
{
    const M = 32768;
    bool[M] not_prime;
    not_prime[0] = true;
    not_prime[1] = true;
    foreach (i; 2..200)
    {
        if (not_prime[i])
        {
            continue;
        }
        foreach (j; iota(i+i, M, i))
        {
            not_prime[j] = true;
        }
    }
    int[] ret;
    foreach (i; 2..M)
    {
        if (!not_prime[i])
        {
            ret ~= i;
        }
    }
    return ret;
}

/// 区別できないe個のボールを区別できるn個の箱へ入れる方法の総数 (mod 10_0000_0007)
int partition(int e, int n)
{
    // dp[i][j] = i箱までに合計j個を入れる方法の総数
    // 漸化式: dp[i][j] = Σdp[i-1][j以下]
    ulong[][] dp;
    dp.length = n+1;
    foreach (i; 0..(n+1))
    {
        dp[i].length = e+1;
    }
    dp[0][0] = 1;
    foreach(i; 0..n)
    {
        foreach (j; 0..(e+1))
        {
            foreach (jj; 0..(j+1))
            {
                dp[i+1][j] += dp[i][jj];
                if (mod <= dp[i+1][j])
                {
                    dp[i+1][j] -= mod;
                }
            }
        }
    }
    return cast(int)(dp[n][e]);
}

Submission Info

Judge Result