結果
問題 | No.1660 Matrix Exponentiation |
ユーザー |
|
提出日時 | 2021-08-27 21:46:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 206 ms / 2,000 ms |
コード長 | 4,484 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 96,684 KB |
最終ジャッジ日時 | 2024-11-21 01:31:29 |
合計ジャッジ時間 | 4,204 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
def floor_sum(n: int, m: int, a: int, b: int) -> int:ans = 0if a >= m:ans += (n - 1) * n * (a // m) // 2a %= mif b >= m:ans += n * (b // m)b %= my_max = (a * n + b) // mx_max = y_max * m - bif y_max == 0:return ansans += (n - (x_max + a - 1) // a) * y_maxans += floor_sum(y_max, a, m, (a - x_max % a) % a)return ansdef divisors(M):d=[]i=1while M>=i**2:if M%i==0:d.append(i)if i**2!=M:d.append(M//i)i=i+1return ddef popcount(x):x = x - ((x >> 1) & 0x55555555)x = (x & 0x33333333) + ((x >> 2) & 0x33333333)x = (x + (x >> 4)) & 0x0f0f0f0fx = x + (x >> 8)x = x + (x >> 16)return x & 0x0000007fdef eratosthenes(n):res=[0 for i in range(n+1)]prime=set([])for i in range(2,n+1):if not res[i]:prime.add(i)for j in range(1,n//i+1):res[i*j]=1return primedef factorization(n):res=[]for p in prime:if n%p==0:while n%p==0:n//=pres.append(p)if n!=1:res.append(n)return resdef euler_phi(n):res = nfor x in range(2,n+1):if x ** 2 > n:breakif n%x==0:res = res//x * (x-1)while n%x==0:n //= xif n!=1:res = res//n * (n-1)return resdef ind(b,n):res=0while n%b==0:res+=1n//=breturn resdef isPrimeMR(n):if n==1:return 0d = n - 1d = d // (d & -d)L = [2, 3, 5, 7, 11, 13, 17]if n in L:return 1for a in L:t = dy = pow(a, t, n)if y == 1: continuewhile y != n - 1:y = (y * y) % nif y == 1 or t == n - 1: return 0t <<= 1return 1def findFactorRho(n):from math import gcdm = 1 << n.bit_length() // 8for c in range(1, 99):f = lambda x: (x * x + c) % ny, r, q, g = 2, 1, 1, 1while g == 1:x = yfor i in range(r):y = f(y)k = 0while k < r and g == 1:ys = yfor i in range(min(m, r - k)):y = f(y)q = q * abs(x - y) % ng = gcd(q, n)k += mr <<= 1if g == n:g = 1while g == 1:ys = f(ys)g = gcd(abs(x - ys), n)if g < n:if isPrimeMR(g): return gelif isPrimeMR(n // g): return n // greturn findFactorRho(g)def primeFactor(n):i = 2ret = {}rhoFlg = 0while i*i <= n:k = 0while n % i == 0:n //= ik += 1if k: ret[i] = ki += 1 + i % 2if i == 101 and n >= 2 ** 20:while n > 1:if isPrimeMR(n):ret[n], n = 1, 1else:rhoFlg = 1j = findFactorRho(n)k = 0while n % j == 0:n //= jk += 1ret[j] = kif n > 1: ret[n] = 1if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}return retdef divisors(n):res = [1]prime = primeFactor(n)for p in prime:newres = []for d in res:for j in range(prime[p]+1):newres.append(d*p**j)res = newresres.sort()return resimport sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import gcd,loginput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())N,K = mi()edge = [[] for v in range(N)]deg = [0 for v in range(N)]for _ in range(K):u,v = mi()edge[u-1].append(v-1)deg[v-1] += 1deq = deque([v for v in range(N) if not deg[v]])topo = []while deq:v = deq.popleft()topo.append(v)for nv in edge[v]:deg[nv] -= 1if deg[nv]==0:deq.append(nv)if len(topo)!=N:exit(print(-1))dp = [0 for v in range(N)]for v in topo[::-1]:for nv in edge[v]:dp[v] = max(dp[v],dp[nv]+1)print(max(dp)+1)