結果
問題 | No.315 世界のなんとか3.5 |
ユーザー |
![]() |
提出日時 | 2023-02-02 14:35:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 595 ms / 2,000 ms |
コード長 | 2,630 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 126,236 KB |
最終ジャッジ日時 | 2024-07-02 03:42:12 |
合計ジャッジ時間 | 13,626 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
import bisectimport copyimport decimalimport fractionsimport heapqimport itertoolsimport mathimport randomimport sysimport timefrom collections import Counter,deque,defaultdictfrom functools import lru_cache,reducefrom heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_maxdef _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], itemheapq._siftup_max(heap, 0)return itemfrom math import gcd as GCDread=sys.stdin.readreadline=sys.stdin.readlinereadlines=sys.stdin.readlineswrite=sys.stdout.writeA,B,P=readline().split()A=list(map(int,list(A)))B=list(map(int,list(B)))P=int(P)mod=10**9+7def solve(N):if len(N)<=6:ans=0N=int("".join(map(str,N)))for n in range(1,N):if (n%3==0 or "3" in str(n)) and n%P:ans+=1return ansdp0=[0]*3dp1=[0]*3for i in range(1,N[0]):if i==3:dp1[i%3]+=1else:dp0[i%3]+=1s=N[0]bl=(N[0]==3)for n in N[1:-5]:prev0=dp0prev1=dp1dp0=[0]*3dp1=[0]*3for p in range(3):for i in range(10):if i==3:dp1[(p+i)%3]+=prev0[p]dp1[(p+i)%3]+=prev1[p]dp1[(p+i)%3]%=modelse:dp0[(p+i)%3]+=prev0[p]dp1[(p+i)%3]+=prev1[p]dp0[(p+i)%3]%=moddp1[(p+i)%3]%=modfor i in range(n):if bl|(i==3):dp1[(s+i)%3]+=1else:dp0[(s+i)%3]+=1for i in range(1,10):if i==3:dp1[i%3]+=1else:dp0[i%3]+=1s=(s+n)%3bl|=(n==3)X=N[-5]*10000+N[-4]*1000+N[-3]*100+N[-2]*10+N[-1]ans=0for i in range(3):for x in range(100000):if x%P==0:continueif (i+x)%3==0 or "3" in str(x):ans+=dp0[i]ans+=dp1[i]for x in range(1,X):if x%P==0:continueif (s+x)%3==0 or "3" in str(x) or bl:ans+=1for x in range(1,100000):if x%P==0:continueif x%3==0 or "3" in str(x):ans+=1return ans%modans=(solve(B)-solve(A))%modB=[0]*4+Bif (3 in B or sum(B)%3==0) and (B[-5]*10000+B[-4]*1000+B[-3]*100+B[-2]*10+B[-1])%P!=0:ans+=1ans%=modprint(ans)