Kaosar və Ardıcıllıqlar#12327

Kaosar və Ardıcıllıqlar (Həll təhlili)

Problem Müəllifi:	AlKaosar Hussain
Hazırlayan:	AlKaosar Hussain
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Burada ardıcıllığın ilk dəyəri $1$ -dir və son dəyəri $n$ -dir, qalan hər bitişik

dəyər bir-birini bölür və onların nisbəti asal ədəd olmalıdır, indi asal faktorizasiyanı

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}}

götürək.

İndi əsas müşahidə odur ki, hər addımda cari ədəd $a_{i}$ a_i-ni dəqiq bir asal ədəd $p_{j}$ p_j ilə vurursunuz

və hər bir asal $p_{j}$ p_j $n$ -də $c_{j}$ c_j dəfə baş verir, çünki siz bir vaxtda bir asal ilə vurursunuz,

hər bir asalın eksponenti bir-bir əlavə edilməlidir, beləliklə $n$ -ə çatmaq üçün toplam addımlar $n = \sum c_{i}$ n=\sum c_i-dir. $1$ -dən başlayaraq

maksimum ardıcıllıq uzunluğu = $1 + \sum c_{i}$ 1+\sum c_i.

İndi sizdə $c_{i}$ c_i ədəd $p_{i}$ p_i var, ardıcıllıqda hər addımda bir asal nüsxəsini seçməli və onu vurmalısınız

çünki sıralama əhəmiyyətlidir, çünki fərqli sıralamalar fərqli ardıcıllıqlar yaradır, beləliklə, başlanğıc $1 = \sum c_{i}$ 1=\sum c_i-ni istisna edərək toplam addımlar

və fərqli ardıcıllıqların sayı =

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

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

bu, multinomial koeffisiyentdir və cavab budur.

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