結果

問題 No.1973 Divisor Sequence
ユーザー taiga0629kyoprotaiga0629kyopro
提出日時 2022-06-12 11:11:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 96 ms / 2,000 ms
コード長 2,830 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 76,120 KB
最終ジャッジ日時 2024-09-22 21:38:01
合計ジャッジ時間 2,401 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
54,400 KB
testcase_01 AC 38 ms
55,132 KB
testcase_02 AC 43 ms
60,888 KB
testcase_03 AC 44 ms
60,116 KB
testcase_04 AC 43 ms
60,588 KB
testcase_05 AC 52 ms
59,320 KB
testcase_06 AC 43 ms
61,208 KB
testcase_07 AC 46 ms
59,096 KB
testcase_08 AC 43 ms
60,584 KB
testcase_09 AC 44 ms
59,920 KB
testcase_10 AC 46 ms
61,844 KB
testcase_11 AC 43 ms
60,944 KB
testcase_12 AC 43 ms
59,928 KB
testcase_13 AC 44 ms
60,536 KB
testcase_14 AC 52 ms
65,624 KB
testcase_15 AC 42 ms
58,764 KB
testcase_16 AC 43 ms
60,288 KB
testcase_17 AC 47 ms
63,000 KB
testcase_18 AC 49 ms
63,092 KB
testcase_19 AC 44 ms
61,004 KB
testcase_20 AC 44 ms
60,204 KB
testcase_21 AC 43 ms
60,080 KB
testcase_22 AC 44 ms
59,984 KB
testcase_23 AC 96 ms
76,120 KB
testcase_24 AC 55 ms
65,280 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod=10**9+7


#####################
def mul(a,b):
    n=len(a)
    m=len(b[0])
    res=[[0]*m for i in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(len(a[0])):
                res[i][j]+=a[i][k]*b[k][j]
                res[i][j]%=mod
    return res
def mpow(a,n):
    N = len(a)
    if n == 0:
        res = [[0] * N for i in range(N)]
        for i in range(N):
            res[i][i] = 1
        return res
    if n==1:return a
    res=mpow(a,n//2)
    res=mul(res,res)
    if n%2==1:
        res=mul(res,a)
    return res


def det(A):
    a=[]
    for line in A:
        a.append(line[:])

    n=len(a)
    f=1
    for now in range(n):
        ind=-1
        for i in range(now,n):
            a[i][now]%=mod
            if a[i][now]>0:
                ind=i
                break
        if ind==-1:return 0
        a[now],a[ind]=a[ind],a[now]
        if now!=ind:f*=-1
        f=f*a[now][now]%mod
        inv=pow(a[now][now],mod-2,mod)
        for j in range(now,n):
            a[now][j]*=inv
            a[now][j]%=mod
        for i in range(now+1,n):
            x=a[i][now]
            for j in range(now,n):
                a[i][j]-=a[now][j]*x
                a[i][j]%=mod
    for i in range(n):
        f*=a[i][i]
        f%=mod
    return f


def minv(A):
    n=len(A)
    if det(A)==0:return -1
    a=[]
    for i in range(n):
        e=[0]*n
        e[i]=1
        a.append(A[i][:]+e)
    for now in range(n):
        ind = -1
        for i in range(now, n):
            a[i][now] %= mod
            if a[i][now] > 0:
                ind = i
                break
        if ind == -1: return -1
        a[now], a[ind] = a[ind], a[now]
        inv = pow(a[now][now], mod - 2, mod)
        for j in range(now, 2*n):
            a[now][j] *= inv
            a[now][j] %= mod
        for i in range(now + 1, n):
            x = a[i][now]
            for j in range(now, 2*n):
                a[i][j] -= a[now][j] * x
                a[i][j] %= mod
    for now in range(n-1,-1,-1):
        for i in range(now-1,-1,-1):
            x=a[i][now]
            for j in range(2*n):
                a[i][j]-=a[now][j]*x
                a[i][j]%=mod
    res=[]
    for l in a:res.append(l[n:])
    return res


#######################



from _collections import defaultdict
n,m=map(int,input().split())
x=m
d=defaultdict(int)
for p in range(2,m+1):
    if p**2>x:break
    while x%p==0:
        x//=p
        d[p]+=1
if x>1:d[x]+=1

ans=1
for p in d:
    k=d[p]
    a=[[0]*(k+1) for i in range(k+1)]
    for x in range(k+1):
        for y in range(k+1):
            if x+y<=k:
                a[x][y]+=1
    dp=[[0] for i in range(k+1)]
    dp[0][0]=1
    a=mpow(a,n)
    dp=mul(a,dp)
    res=0
    for x in range(k+1):
        res+=dp[x][0]
    ans*=res
    ans%=mod
print(ans)
0