Каосар та послідовності#12327

Каосар та послідовності (Розбір)

Автор задачі:	AlKaosar Hussain
Підготовлено:	AlKaosar Hussain
Редагував:	Hasan Saleh (MathModel)

Розв'язок

Тут перше значення послідовності $1$ , а останнє значення $n$ , і всі інші сусідні

значення ділять один одного, а їх співвідношення є простим числом. Нехай розклад на прості множники

n = p_{1}^{c_{1}} p_{2}^{c_{2}} \dots p_{m}^{c_{m}}

n = p_{1}^{c_{1}} p_{2}^{c_{2}} \dots p_{m}^{c_{m}}

Тепер основне спостереження полягає в тому, що на кожному кроці ви множите поточне число $a_{i}$ a_i на точно один простий

$p_{j}$ p_j, і кожен простий $p_{j}$ p_j зустрічається $c_{j}$ c_j разів у $n$ , оскільки ви можете множити лише на один простий за раз,

кожен показник простого повинен додаватися по одному, тому загальна кількість кроків, щоб досягти $n = \sum c_{i}$ n=\sum c_i. Включаючи початок з $1$ ,

максимальна довжина послідовності = $1 + \sum c_{i}$ 1+\sum c_i.

Тепер у вас є $c_{i}$ c_i копій $p_{i}$ p_i, на кожному кроці в послідовності потрібно вибрати одну копію простого і помножити її,

оскільки порядок має значення, адже різні порядки дають різні послідовності, тому загальна кількість кроків, не враховуючи

початковий $1 = \sum c_{i}$ 1=\sum c_i. А кількість різних послідовностей =

\frac{( \sum c _{i} )!}{\prod c _{i} !} mod 1 0^{9} + 7

\frac{(\sum c_i)!}{\prod c_i!}\mod 10^9+7

що є мультиномиальним коефіцієнтом, і це відповідь.

MOD = 10**9 + 7
MAXN = 10000
fact = [1] * (MAXN + 1)
invfact = [1] * (MAXN + 1)
for i in range(2, MAXN + 1):
    fact[i] = fact[i - 1] * i % MOD
invfact[MAXN] = pow(fact[MAXN], MOD - 2, MOD)
for i in range(MAXN, 0, -1):
    invfact[i - 1] = invfact[i] * i % MOD
def prime(n):
    factors = {}
    x = n
    p = 2
    while p * p <= x:
        while x % p == 0:
            factors[p] = factors.get(p, 0) + 1
            x //= p
        p += 1
    if x > 1:
        factors[x] = factors.get(x, 0) + 1
    return factors
def multinomial(exp):
    total = sum(exp)
    if total == 0:
        return -1 
    res = fact[total]
    for e in exp:
        res = res * invfact[e] % MOD
    return total, res
def solve(n):
    factors = prime(n)
    exp = list(factors.values())
    return multinomial(exp)
for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print(1,1)
        continue
    a, b = solve(n)
    print(b % MOD,a+1)

Python