結果
問題 | No.1973 Divisor Sequence |
ユーザー | vwxyz |
提出日時 | 2023-11-21 04:36:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,812 ms / 2,000 ms |
コード長 | 2,842 bytes |
コンパイル時間 | 325 ms |
コンパイル使用メモリ | 81,896 KB |
実行使用メモリ | 91,500 KB |
最終ジャッジ日時 | 2024-09-26 06:58:00 |
合計ジャッジ時間 | 15,727 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 165 ms
89,420 KB |
testcase_01 | AC | 163 ms
89,096 KB |
testcase_02 | AC | 895 ms
91,084 KB |
testcase_03 | AC | 243 ms
91,372 KB |
testcase_04 | AC | 602 ms
91,084 KB |
testcase_05 | AC | 288 ms
90,940 KB |
testcase_06 | AC | 583 ms
91,376 KB |
testcase_07 | AC | 263 ms
91,204 KB |
testcase_08 | AC | 415 ms
91,224 KB |
testcase_09 | AC | 555 ms
91,228 KB |
testcase_10 | AC | 672 ms
91,140 KB |
testcase_11 | AC | 270 ms
91,020 KB |
testcase_12 | AC | 565 ms
91,472 KB |
testcase_13 | AC | 319 ms
91,280 KB |
testcase_14 | AC | 490 ms
91,164 KB |
testcase_15 | AC | 808 ms
91,216 KB |
testcase_16 | AC | 772 ms
90,952 KB |
testcase_17 | AC | 591 ms
91,312 KB |
testcase_18 | AC | 240 ms
91,292 KB |
testcase_19 | AC | 707 ms
91,500 KB |
testcase_20 | AC | 287 ms
91,100 KB |
testcase_21 | AC | 759 ms
91,172 KB |
testcase_22 | AC | 694 ms
91,148 KB |
testcase_23 | AC | 1,156 ms
90,956 KB |
testcase_24 | AC | 1,812 ms
91,204 KB |
ソースコード
import bisect import copy import decimal import fractions import heapq import itertools import math import random import sys import time from collections import Counter,deque,defaultdict from functools import lru_cache,reduce from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max def _heappush_max(heap,item): heap.append(item) heapq._siftdown_max(heap, 0, len(heap)-1) def _heappushpop_max(heap, item): if heap and item < heap[0]: item, heap[0] = heap[0], item heapq._siftup_max(heap, 0) return item from math import gcd as GCD read=sys.stdin.read readline=sys.stdin.readline readlines=sys.stdin.readlines write=sys.stdout.write #import pypyjit #pypyjit.set_param('max_unroll_recursion=-1') #sys.set_int_max_str_digits(10**9) def Factorize(N): assert N>=1 factors=defaultdict(int) for p in range(2,N): if p**2>N: break while N%p==0: factors[p]+=1 N//=p if N!=1: factors[N]+=1 return factors class Cumsum: def __init__(self,lst,mod=0): self.N=len(lst) self.mod=mod self.cumsum=[0]*(self.N+1) self.cumsum[0]=0 for i in range(1,self.N+1): self.cumsum[i]=self.cumsum[i-1]+lst[i-1] if self.mod: self.cumsum[i]%=self.mod def __getitem__(self,i): if type(i)==int: if 0<=i<self.N: a,b=i,i+1 elif -self.N<=i<0: a,b=i+self.N,i+self.N+1 else: raise IndexError('list index out of range') else: a,b=i.start,i.stop if a==None or a<-self.N: a=0 elif self.N<=a: a=self.N elif a<0: a+=self.N if b==None or self.N<=b: b=self.N elif b<-self.N: b=0 elif b<0: b+=self.N s=self.cumsum[b]-self.cumsum[a] if self.mod: s%=self.mod return s def __setitem__(self,i,x): if -self.N<=i<0: i+=self.N elif not 0<=i<self.N: raise IndexError('list index out of range') self.cumsum[i+1]=self.cumsum[i]+x if self.mod: self.cumsum[i+1]%=self.mod def __len__(self): return self.N def __str__(self): lst=[self.cumsum[i+1]-self.cumsum[i] for i in range(self.N)] if self.mod: for i in range(self.N): lst[i]%=self.mod return "["+", ".join(map(str,lst))+"]" N,M=map(int,readline().split()) ans=1 mod=10**9+7 for p,e in Factorize(M).items(): dp=Cumsum([1]+[0]*e,mod=mod) for i in range(N): dp=Cumsum([dp[:e+1-i] for i in range(e+1)],mod=mod) ans*=dp[:] ans%=mod print(ans)