結果

問題 No.2798 Multiple Chain
ユーザー navel_tos
提出日時 2024-06-28 23:11:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 60 ms / 2,000 ms
コード長 3,139 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 68,608 KB
最終ジャッジ日時 2024-06-28 23:11:22
合計ジャッジ時間 4,257 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder 2798 Multiple Chain

#O(N ^ {1/4}) 高速素因数分解
def fast_fact(N):
    import random
    gcd = lambda x,y: gcd(y, x % y) if y else abs(x)

    #Miller-Rabin Primality Test  O(logN) time, wrong rate: under 1/4 per test.
    def check_prime(n):
        if n == 1 or n % 2 == 0: return True if n == 2 else False
        m = n - 1; s = (m & -m).bit_length() - 1; d = m // pow(2, s)  #m = d * 2^s 
        if n < 48781 * 97561: test_number = [2, 7, 61]
        else: test_number = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
        if n > pow(2, 64): test_number.extend([random.randint(3, m) for _ in range(10)])
        for a in test_number:
            x, r = pow(a, d, n), 0
            if a == n or x == 1: continue
            while x != m:
                x, r = pow(x, 2, n), r + 1
                if x == 1 or r == s: return False
        return True

    #Pollards rho algorithm
    def find_prime(n):
        if n % 2 == 0: return 2
        m = int(n ** 0.125) + 1
        for c in range(1, n):
            f, x, y, k, g, q, r = lambda x: (pow(x, 2, n) + c) % n, 0, 0, 0, 1, 1, 1
            while g == 1:  #y = f^k(c), x = f^{r/2}(c).  especially, r is power of 2
                while k < 3 * r // 4: y, k = f(y), k + 1  #skip calculate
                while k < r and g == 1:
                    s = y
                    for _ in range(min(m, r - k)): y = f(y); q = q * abs(x - y) % n
                    g, k = gcd(q, n), k + m
                k, r, x = r, r * 2, y
            if g == n:  #backtrack
                g, y = 1, s
                while g == 1: y = f(y); g = gcd(abs(x - y), n)
            if g == n: continue
            return g if check_prime(g) else n//g if check_prime(n//g) else find_prime(g)
        return n  #RE prevention
                    
    A = []
    while not check_prime(N) and N > 1:
        P, E = find_prime(N), 0
        while N % P == 0: N, E = N // P, E + 1
        A.append((P, E))
    if N > 1: A.append((N, 1))
    return sorted(A)


#入力受取
N = int(input())

#素因数分解  因数の個数を列挙
P = fast_fact(N)
Q = sorted(e for f, e in P)
R = max(Q)

#分割数を考える
#DP[n][k]: 自然数nをk個の「非負整数」の和として表す場合の数
#これは蟻本式DPでO(n^2)  DP[n][k] = DP[n][k - 1] + DP[n - k][k]
#k個のなかに0を含むものはDP[n][k - 1]通り
#k個のなかに0を含まないものはDP[n - k][k]通り
DP = [[0] * 64 for _ in range(64)]
for k in range(64):
    DP[0][k] = 1
for n in range(1, 64):
    for k in range(1, 64):
        DP[n][k] = DP[n][k - 1]
        if n >= k: DP[n][k] += DP[n - k][k]

#長さxの数列であって、分割を満たすものの個数。ただし、全要素の先頭が0ではだめ。
def solve(x):
    #1. 全要素を長さxに分割する場合の数の積を求める
    ans = 1
    for q in Q:
        ans *= DP[q][x]

    #2. 全要素の先頭が0であるものの個数を求める
    if x == 1:
        return ans
    cnt = 1
    for q in Q:
        cnt *= DP[q][x - 1]
    return ans - cnt

ans = 0
for x in range(1, R + 1):
    ans += solve(x)
print(ans)
0