結果
| 問題 |
No.1750 ラムドスウイルスの感染拡大-hard
|
| コンテスト | |
| ユーザー |
 Dai_7_Gon
|
| 提出日時 | 2021-11-20 02:54:05 |
| 言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,007 bytes |
| コンパイル時間 | 395 ms |
| コンパイル使用メモリ | 13,056 KB |
| 実行使用メモリ | 34,816 KB |
| 最終ジャッジ日時 | 2025-01-02 08:56:58 |
| 合計ジャッジ時間 | 14,823 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 WA * 1 |
| other | AC * 6 WA * 24 |
ソースコード
import sys
import re
import random
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)
import numpy as np
# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
def nck(n, k, kaijyo):
return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD
def npk(n, k, kaijyo):
if k == 0 or k == n:
return n % MOD
return (kaijyo[n] * divide(kaijyo[n-k])) % MOD
def fact_and_inv(SIZE):
inv = [0] * SIZE # inv[j] = j^{-1} mod MOD
fac = [0] * SIZE # fac[j] = j! mod MOD
finv = [0] * SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2, SIZE):
inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
fac[i] = fac[i - 1] * i % MOD
finv[i] = finv[i - 1] * inv[i] % MOD
return fac, finv
def renritsu(A, Y):
# example 2x + y = 3, x + 3y = 4
# A = [[2,1], [1,3]])
# Y = [[3],[4]] または [3,4]
A = np.matrix(A)
Y = np.matrix(Y)
Y = np.reshape(Y, (-1, 1))
X = np.linalg.solve(A, Y)
# [1.0, 1.0]
return X.flatten().tolist()[0]
class TwoDimGrid:
# 2次元座標 -> 1次元
def __init__(self, h, w, wall="#"):
self.h = h
self.w = w
self.size = (h+2) * (w+2)
self.wall = wall
self.get_grid()
# self.init_cost()
def get_grid(self):
grid = [self.wall * (self.w + 2)]
for i in range(self.h):
grid.append(self.wall + getS() + self.wall)
grid.append(self.wall * (self.w + 2))
self.grid = grid
def init_cost(self):
self.cost = [INF] * self.size
def pos(self, x, y):
# 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
return y * (self.w + 2) + x
def getgrid(self, x, y):
return self.grid[y][x]
def get(self, x, y):
return self.cost[self.pos(x, y)]
def set(self, x, y, v):
self.cost[self.pos(x, y)] = v
return
def show(self):
for i in range(self.h+2):
print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
def showsome(self, tgt):
for t in tgt:
print(t)
return
def showsomejoin(self, tgt):
for t in tgt:
print("".join(t))
return
def search(self):
grid = self.grid
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
# for i in range(1, self.h+1):
# for j in range(1, self.w+1):
# cx, cy = j, i
# for dx, dy in move:
# nx, ny = dx + cx, dy + cy
class BIT():
# A1 ... AnのBIT(1-indexed)
def __init__(self, n):
self.n = n
self.BIT = [0] * (n + 2)
# A1 ~ Aiまでの和 O(logN)
def query(self, idx):
res_sum = 0
while idx > 0:
res_sum += self.BIT[idx]
idx -= idx & (-idx)
return res_sum
# Ai += x O(logN)
def update(self, idx, x):
# print(idx)
while idx <= self.n:
# print(idx)
self.BIT[idx] += x
idx += idx & (-idx)
return
def show(self):
print(self.BIT)
def set_graph(n, m):
"""
set graph (n vertex, m edges)
"""
g = [[] for i in range(n)]
for i in range(m):
a, b = getZList()
g[a].append(b)
g[b].append(a)
return g
def set_graph_with_cost(n, m):
"""
set graph (n vertex, m edges)
"""
g = [[] for i in range(n)]
for i in range(m):
a, b, c = getZList()
c += 1
g[a].append([c, b])
g[b].append([c, a])
return g
def set_grid(n):
g = []
for i in range(n):
g.append(getList())
return g
def point_to_degree(dx, dy):
"""
return: 0 ~ 360
"""
if dx == 0:
if dy < 0:
d = 270
else:
d = 90
else:
d = math.degrees(math.atan(dy / dx))
if dx <= 0 and dy >= 0:
d = 180 + d
elif dx <= 0 and dy <= 0:
d = 180 + d
elif dx >= 0 and dy <= 0:
d = 360 + d
return d
def zero_one_bfs(graph, start, n):
d = deque([start])
costs = [INF] * n;
costs[start] = 0
while d:
cur = d.popleft()
cost = costs[cur]
for tgt in graph[cur]:
if costs[tgt] == INF:
costs[tgt] = cost + 1
d.append(tgt)
return costs
def cutoff_zero_one_bfs(graph, start, n, cutoff, gg):
h = deque()
h.append(start)
costs = [INF for _ in range(n)]
costs[start] = 0
while h:
cur = h.popleft()
cost = costs[cur]
for edge in graph[cur]:
tgt = edge
if costs[tgt] == INF and gg[tgt] >= cutoff:
costs[tgt] = cost+1
h.append(tgt)
return costs
def solve():
mod = 998244353
n,m,t = getList()
# t = 2
g = [[0 for i in range(n)] for j in range(n)]
for i in range(m):
a,b = getList()
g[a][b] = 1
g[b][a] = 1
mat = np.matrix(g)
# print(mat)
fmat = np.eye(n)
while t:
if t % 2:
fmat = np.dot(fmat, mat)
mat = np.dot(mat, mat)
t >>= 1
mat %= mod
fmat %= mod
print(int(fmat[0, 0] // 1))
def ran():
n = random.randint(1, 100)
li = [random.choice(["B", "R", "W"]) for i in range(n)]
return n, li
def main():
n = getN()
for _ in range(n):
solve()
return
if __name__ == "__main__":
# main()
solve()