提出 #55754435

---

ソースコード 拡げる

from collections import defaultdict

MOD=998244353
MAX_PRIME=6
PRIMES=[2,3,5,7,11,13]

def matrix_pow(a,x):
    mat_size=len(a)
    ret=[[0]*mat_size for _ in range(mat_size)]
    for i in range(mat_size):
        ret[i][i]=1
    while x>0:
        if x&1:
            nret=[[0]*mat_size for _ in range(mat_size)]
            for i in range(mat_size):
                for k in range(mat_size):
                    for j in range(mat_size):
                        nret[i][j]+=ret[i][k]*a[k][j]
                        nret[i][j]%=MOD
            ret=nret
        na=[[0]*mat_size for _ in range(mat_size)]
        for i in range(mat_size):
            for k in range(mat_size):
                for j in range(mat_size):
                    na[i][j]+=a[i][k]*a[k][j]
                    na[i][j]%=MOD
        a=na
        x>>=1
    return ret

N,M=map(int,input().split())
mat=[[0]*((1<<MAX_PRIME)+1) for _ in range((1<<MAX_PRIME)+1)]
nxt=defaultdict(int)
for i in range(1<<MAX_PRIME):
    for j in range(1,M+1):
        add=1
        for k in range(MAX_PRIME):
            if not (i>>k)&1:
                continue
            cnt=0
            while j%PRIMES[k]==0:
                cnt+=1
                j//=PRIMES[k]
            add*=cnt
        nxt[i]+=add
for i in range(1<<MAX_PRIME):
    for j in nxt:
        if (i&j)==0:
            mat[i][i|j]+=nxt[j]
mat[(1<<MAX_PRIME)-1][1<<MAX_PRIME]=1
mat[1<<MAX_PRIME][1<<MAX_PRIME]=1
mat=matrix_pow(mat,N+1)
ans=0
for i in range(1<<MAX_PRIME):
    ans+=mat[i][1<<MAX_PRIME]
print((ans-1)%MOD)

提出情報

ジャッジ結果