結果

問題 No.1532 Different Products
ユーザー chineristAC
提出日時 2021-05-02 04:38:30
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,401 bytes
コンパイル時間 551 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 92,800 KB
最終ジャッジ日時 2024-07-21 02:15:08
合計ジャッジ時間 15,584 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 11 WA * 2 RE * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
Dirichlet Product
"""
def mul(N,K,L,data_as,data_ab,data_bs,data_bb):
    data_rs = [0 for i in range(K+1)]
    data_rb = [0 for i in range(L+1)]

    for i in range(1,K+1):
        for j in range(1,K//i+1):
            data_rs[i*j] += data_as[i] * data_bs[j]

    data_as_cum = [data_as[i] for i in range(K+1)]
    data_bs_cum = [data_bs[i] for i in range(K+1)]
    for i in range(1,K+1):
        data_as_cum[i] += data_as_cum[i-1]
        data_bs_cum[i] += data_bs_cum[i-1]

    def cumA(i):
        if 1<=i<=L:
            return data_ab[i]
        else:
            return data_as_cum[(N//i)]

    def cumB(i):
        if 1<=i<=L:
            return data_bb[i]
        else:
            return data_bs_cum[(N//i)]

    for i in range(1,L+1):
        M = int((N//i)**.5)
        for j in range(1,M+1):
            data_rb[i] += data_as[j] * cumB(i*j)
        for j in range(1,M+1):
            data_rb[i] += data_bs[j] * (cumA(i*j)-cumA(N//M))

    return data_rs,data_rb

def single_mul(N,K,L,a,A,val):
    res = [a[i] for i in range(K+1)]
    Res = [A[i] for i in range(L+1)]

    for i in range(1,K+1):
        if i*val<=K:
            res[i*val] += a[i]

    cum = [a[i] for i in range(K+1)]
    for i in range(1,K+1):
        cum[i] += cum[i-1]

    def cumA(i):
        if 1<=i<=L:
            return A[i]
        else:
            return cum[N//i]

    for i in range(1,L+1):
        Res[i] += cumA(i*val)

    return res,Res

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd,log

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

N,K = mi()

M = 10000
dp = [[0 for j in range(M+1)] for i in range(N+2)]
dp[N+1][1] = 1
for i in range(N,0,-1):
    for j in range(1,M+1):
        dp[i][j] += dp[i+1][j]
        if j*i <= M:
            dp[i][j*i] += dp[i+1][j]

for i in range(1,N+2):
    for j in range(2,M+1):
        dp[i][j] += dp[i][j-1]

stack = [(1,1)]
res = -1
while stack:
    val,L = stack.pop()
    if val<10**5:
        res += 1
        for i in range(L,N+1):
            if val*i <= K:
                if val*i >= 10**5:
                    res += (dp[i+1][K//(val*i)])
                else:
                    stack.append((val*i,i+1))
            else:
                break

print(res%998244353)
0