#694924 (Python3) No.329 全射

提出ソース
結果

問題	No.329 全射
ユーザー	vwxyz
提出日時	2021-09-03 19:09:29
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	1,519 ms / 2,000 ms
コード長	25,002 bytes
コンパイル時間	712 ms
コンパイル使用メモリ	15,232 KB
実行使用メモリ	44,020 KB
最終ジャッジ日時	2024-12-15 06:24:15
合計ジャッジ時間	23,671 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	252 ms 38,272 KB
testcase_01	AC	239 ms 38,144 KB
testcase_02	AC	247 ms 38,400 KB
testcase_03	AC	239 ms 38,272 KB
testcase_04	AC	251 ms 38,144 KB
testcase_05	AC	235 ms 38,272 KB
testcase_06	AC	237 ms 38,144 KB
testcase_07	AC	239 ms 38,144 KB
testcase_08	AC	240 ms 38,144 KB
testcase_09	AC	238 ms 38,272 KB
testcase_10	AC	244 ms 38,272 KB
testcase_11	AC	236 ms 38,144 KB
testcase_12	AC	236 ms 38,144 KB
testcase_13	AC	1,369 ms 42,988 KB
testcase_14	AC	432 ms 39,296 KB
testcase_15	AC	794 ms 41,088 KB
testcase_16	AC	1,183 ms 42,880 KB
testcase_17	AC	999 ms 41,728 KB
testcase_18	AC	1,519 ms 44,020 KB
testcase_19	AC	1,446 ms 42,880 KB
testcase_20	AC	1,426 ms 42,976 KB
testcase_21	AC	1,130 ms 41,976 KB
testcase_22	AC	976 ms 41,088 KB
testcase_23	AC	577 ms 40,832 KB
testcase_24	AC	520 ms 40,448 KB
testcase_25	AC	790 ms 41,088 KB
testcase_26	AC	490 ms 39,808 KB
testcase_27	AC	264 ms 38,656 KB
testcase_28	AC	242 ms 38,400 KB
testcase_29	AC	259 ms 38,400 KB
testcase_30	AC	253 ms 38,528 KB
testcase_31	AC	237 ms 38,272 KB
testcase_32	AC	261 ms 38,528 KB
testcase_33	AC	260 ms 38,272 KB
testcase_34	AC	260 ms 38,272 KB
testcase_35	AC	275 ms 38,272 KB
testcase_36	AC	262 ms 38,272 KB
testcase_37	AC	261 ms 38,272 KB
testcase_38	AC	260 ms 38,400 KB
testcase_39	AC	258 ms 38,528 KB
testcase_40	AC	260 ms 38,400 KB
testcase_41	AC	253 ms 38,272 KB
testcase_42	AC	267 ms 38,400 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import bisect
import copy
import decimal
import fractions
import functools
import heapq
import itertools
import math
import random
import sys
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

class Graph:
    def __init__(self,V,edges=False,graph=False,directed=False,weighted=False):
        self.V=V
        self.directed=directed
        self.weighted=weighted
        if not graph:
            self.edges=edges
            self.graph=[[] for i in range(self.V)]
            if weighted:
                for i,j,d in self.edges:
                    self.graph[i].append((j,d))
                    if not self.directed:
                        self.graph[j].append((i,d))
            else:
                for i,j in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)
        else:
            self.graph=graph
            self.edges=[]
            for i in range(self.V):
                if self.weighted:
                    for j,d in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j,d))
                else:
                    for j in self.graph[i]:
                        if self.directed or not self.directed and i<=j:
                            self.edges.append((i,j))

    def SS_BFS(self,s,bipartite_graph=False,linked_components=False,parents=False,unweighted_dist=False,weighted_dist=False):
        seen=[False]*self.V
        seen[s]=True
        if linked_components:
            lc=[s]
        if parents:
            ps=[None]*self.V
            ps[s]=s
        if unweighted_dist or bipartite_graph:
            uwd=[float('inf')]*self.V
            uwd[s]=0
        if weighted_dist:
            wd=[float('inf')]*self.V
            wd[s]=0
        queue=deque([s])
        while queue:
            x=queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    y,d=y
                if not seen[y]:
                    seen[y]=True
                    queue.append(y)
                    if linked_components:
                        lc.append(y)
                    if parents:
                        ps[y]=x
                    if unweighted_dist or bipartite_graph:
                        uwd[y]=uwd[x]+1
                    if weighted_dist:
                        wd[y]=wd[x]+d
        if bipartite_graph:
            bg=[[],[]]
            for tpl in self.edges:
                i,j=tpl[:2] if self.weighted else tpl
                if type(uwd[i])==float or type(uwd[j])==float:
                    continue
                if not uwd[i]%2^uwd[j]%2:
                    bg=False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x])==float:
                        continue
                    bg[uwd[x]%2].append(x)
        tpl=()
        if bipartite_graph:
            tpl+=(bg,)
        if linked_components:
            tpl+=(lc,)
        if parents:
            tpl+=(ps,)
        if unweighted_dist:
            tpl+=(uwd,)
        if weighted_dist:
            tpl+=(wd,)
        if len(tpl)==1:
            tpl=tpl[0]
        return tpl

    def AP_BFS(self,bipartite_graph=False,linked_components=False,parents=False):
        seen=[False]*self.V
        if bipartite_graph:
            bg=[None]*self.V
            cnt=-1
        if linked_components:
            lc=[]
        if parents:
            ps=[None]*self.V
        for s in range(self.V):
            if seen[s]:
                continue
            seen[s]=True
            if bipartite_graph:
                cnt+=1
                bg[s]=(cnt,s&2)
            if linked_components:
                lc.append([s])
            if parents:
                ps[s]=s
            queue=deque([s])
            while queue:
                x=queue.popleft()
                for y in self.graph[x]:
                    if self.weighted:
                        y,d=y
                    if not seen[y]:
                        seen[y]=True
                        queue.append(y)
                        if bipartite_graph:
                            bg[y]=(cnt,bg[x][1]^1)
                        if linked_components:
                            lc[-1].append(y)
                        if parents:
                            ps[y]=x
        if bipartite_graph:
            bg_=bg
            bg=[[[],[]] for i in range(cnt+1)]
            for tpl in self.edges:
                i,j=tpl[:2] if self.weighted else tpl
                if not bg_[i][1]^bg_[j][1]:
                    bg[bg_[i][0]]=False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        tpl=()
        if bipartite_graph:
            tpl+=(bg,)
        if linked_components:
            tpl+=(lc,)
        if parents:
            tpl+=(ps,)
        if len(tpl)==1:
            tpl=tpl[0]
        return tpl

    def SS_DFS(self,s,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,parents=False,postorder=False,preorder=False,subtree_size=False,topological_sort=False,unweighted_dist=False,weighted_dist=False):
        seen=[False]*self.V
        finished=[False]*self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag=True
        if euler_tour:
            et=[]
        if linked_components:
            lc=[]
        if parents or cycle_detection or subtree_size:
            ps=[None]*self.V
            ps[s]=s
        if postorder or topological_sort:
            post=[]
        if preorder:
            pre=[]
        if subtree_size:
            ss=[1]*self.V
        if unweighted_dist or bipartite_graph:
            uwd=[float('inf')]*self.V
            uwd[s]=0
        if weighted_dist:
            wd=[float('inf')]*self.V
            wd[s]=0
        stack=[(s,0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                x,d=stack.pop()
            else:
                x=stack.pop()
            if not seen[x]:
                seen[x]=True
                stack.append((x,d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        y,d=y
                    if not seen[y]:
                        stack.append((y,d) if self.weighted else y)
                        if parents or cycle_detection or subtree_size:
                            ps[y]=x
                        if unweighted_dist or bipartite_graph:
                            uwd[y]=uwd[x]+1
                        if weighted_dist:
                            wd[y]=wd[x]+d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag=False
                            if cycle_detection:
                                cd=(y,x)
            elif not finished[x]:
                finished[x]=True
                if euler_tour:
                    et.append(~x)
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if y==ps[x]:
                            continue
                        ss[x]+=ss[y]
        if bipartite_graph:
            bg=[[],[]]
            for tpl in self.edges:
                i,j=tpl[:2] if self.weighted else tpl
                if type(uwd[i])==float or type(uwd[j])==float:
                    continue
                if not uwd[i]%2^uwd[j]%2:
                    bg=False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x])==float:
                        continue
                    bg[uwd[x]%2].append(x)
        tpl=()
        if bipartite_graph:
            tpl+=(bg,)
        if cycle_detection:
            if dag:
                cd=[]
            else:
                y,x=cd
                cd=self.Route_Restoration(y,x,ps)
            tpl+=(cd,)
        if directed_acyclic:
            tpl+=(dag,)
        if euler_tour:
            tpl+=(et,)
        if linked_components:
            tpl+=(lc,)
        if parents:
            tpl+=(ps,)
        if postorder:
            tpl+=(post,)
        if preorder:
            tpl+=(pre,)
        if subtree_size:
            tpl+=(ss,)
        if topological_sort:
            if dag:
                tp_sort=post[::-1]
            else:
                tp_sort=[]
            tpl+=(tp_sort,)
        if unweighted_dist:
            tpl+=(uwd,)
        if weighted_dist:
            tpl+=(wd,)
        if len(tpl)==1:
            tpl=tpl[0]
        return tpl

    def AP_DFS(self,bipartite_graph=False,cycle_detection=False,directed_acyclic=False,euler_tour=False,linked_components=False,parents=False,postorder=False,preorder=False,topological_sort=False):
        seen=[False]*self.V
        finished=[False]*self.V
        if bipartite_graph:
            bg=[None]*self.V
            cnt=-1
        if directed_acyclic or cycle_detection or topological_sort:
            dag=True
        if euler_tour:
            et=[]
        if linked_components:
            lc=[]
        if parents or cycle_detection:
            ps=[None]*self.V
        if postorder or topological_sort:
            post=[]
        if preorder:
            pre=[]
        for s in range(self.V):
            if seen[s]:
                continue
            if bipartite_graph:
                cnt+=1
                bg[s]=(cnt,s&2)
            if linked_components:
                lc.append([])
            if parents:
                ps[s]=s
            stack=[(s,0)] if self.weighted else [s]
            while stack:
                if self.weighted:
                    x,d=stack.pop()
                else:
                    x=stack.pop()
                if not seen[x]:
                    seen[x]=True
                    stack.append((x,d) if self.weighted else x)
                    if euler_tour:
                        et.append(x)
                    if linked_components:
                        lc[-1].append(x)
                    if preorder:
                        pre.append(x)
                    for y in self.graph[x]:
                        if self.weighted:
                            y,d=y
                        if not seen[y]:
                            stack.append((y,d) if self.weighted else y)
                            if bipartite_graph:
                                bg[y]=(cnt,bg[x][1]^1)
                            if parents or cycle_detection:
                                ps[y]=x
                        elif not finished[y]:
                            if directed_acyclic and dag:
                                dag=False
                                if cycle_detection:
                                    cd=(y,x)
                elif not finished[x]:
                    finished[x]=True
                    if euler_tour:
                        et.append(~x)
                    if postorder or topological_sort:
                        post.append(x)
        if bipartite_graph:
            bg_=bg
            bg=[[[],[]] for i in range(cnt+1)]
            for tpl in self.edges:
                i,j=tpl[:2] if self.weighted else tpl
                if not bg_[i][1]^bg_[j][1]:
                    bg[bg_[i][0]]=False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        tpl=()
        if bipartite_graph:
            tpl+=(bg,)
        if cycle_detection:
            if dag:
                cd=[]
            else:
                y,x=cd
                cd=self.Route_Restoration(y,x,ps)
            tpl+=(cd,)
        if directed_acyclic:
            tpl+=(dag,)
        if euler_tour:
            tpl+=(et,)
        if linked_components:
            tpl+=(lc,)
        if parents:
            tpl+=(ps,)
        if postorder:
            tpl+=(post,)
        if preorder:
            tpl+=(pre,)
        if topological_sort:
            if dag:
                tp_sort=post[::-1]
            else:
                tp_sort=[]
            tpl+=(tp_sort,)
        if len(tpl)==1:
            tpl=tpl[0]
        return tpl

    def Tree_Diameter(self,weighted=False):
        def Farthest_Point(u):
            dist=self.SS_BFS(u,weighted_dist=True) if weighted else self.SS_BFS(u,unweighted_dist=True)
            fp=0
            for i in range(self.V):
                if dist[fp]<dist[i]:
                    fp=i
            return fp,dist[fp]
        u,d=Farthest_Point(0)
        v,d=Farthest_Point(u)
        return u,v,d

    def SCC(self):
        reverse_graph=[[] for i in range(self.V)]
        for tpl in self.edges:
            i,j=tpl[:2] if self.weighted else tpl
            reverse_graph[j].append(i)
        postorder=self.AP_DFS(postorder=True)
        scc=[]
        seen=[False]*self.V
        for s in postorder[::-1]:
            if seen[s]:
                continue
            queue=deque([s])
            seen[s]=True
            lst=[]
            while queue:
                x=queue.popleft()
                lst.append(x)
                for y in reverse_graph[x]:
                    if self.weighted:
                        y=y[0]
                    if not seen[y]:
                        seen[y]=True
                        queue.append(y)
            scc.append(lst)
        return scc

    def Build_LCA(self,s):
        self.euler_tour,self.parents,depth=self.SS_DFS(s,euler_tour=True,parents=True,unweighted_dist=True)
        self.dfs_in_index=[None]*self.V
        self.dfs_out_index=[None]*self.V
        for i,x in enumerate(self.euler_tour):
            if x>=0:
                self.dfs_in_index[x]=i
            else:
                self.dfs_out_index[~x]=i
        self.ST=Segment_Tree(2*self.V,lambda x,y:min(x,y),float('inf'))
        lst=[None]*2*self.V
        for i in range(2*self.V):
            if self.euler_tour[i]>=0:
                lst[i]=depth[self.euler_tour[i]]
            else:
                lst[i]=depth[self.parents[~self.euler_tour[i]]]
        self.ST.Build(lst)

    def LCA(self,a,b):
        m=min(self.dfs_in_index[a],self.dfs_in_index[b])
        M=max(self.dfs_in_index[a],self.dfs_in_index[b])
        x=self.euler_tour[self.ST.Fold_Index(m,M+1)]
        if x>=0:
            return x
        else:
            return self.parents[~x]

    def Dijkstra(self,s,route_restoration=False):
        dist=[float('inf')]*self.V
        dist[s]=0
        hq=[(0,s)]
        if route_restoration:
            parents=[None]*self.V
            parents[s]=s
        while hq:
            dx,x=heapq.heappop(hq)
            if dist[x]<dx:
                continue
            for y,dy in self.graph[x]:
                if dist[y]>dx+dy:
                    dist[y]=dx+dy
                    if route_restoration:
                        parents[y]=x
                    heapq.heappush(hq,(dist[y],y))
        if route_restoration:
            return dist,parents
        else:
            return dist

    def Bellman_Ford(self,s,route_restoration=False):
        dist=[float('inf')]*self.V
        dist[s]=0
        if route_restoration:
            parents=[s]*self.V
        for _ in range(self.V-1):
            for i,j,d in self.edges:
                if dist[j]>dist[i]+d:
                    dist[j]=dist[i]+d
                    if route_restoration:
                        parents[j]=i
                if not self.directed and dist[i]>dist[j]+d:
                    dist[i]=dist[j]+d
                    if route_restoration:
                        parents[i]=j
        negative_cycle=[]
        for i,j,d in self.edges:
            if dist[j]>dist[i]+d:
                negative_cycle.append(j)
            if not self.directed and dist[i]>dist[j]+d:
                negative_cycle.append(i)
        if negative_cycle:
            is_negative_cycle=[False]*self.V
            for i in negative_cycle:
                if is_negative_cycle[i]:
                    continue
                else:
                    queue=deque([i])
                    is_negative_cycle[i]=True
                    while queue:
                        x=queue.popleft()
                        for y,d in self.graph[x]:
                            if not is_negative_cycle[y]:
                                queue.append(y)
                                is_negative_cycle[y]=True
                                if route_restoration:
                                    parents[y]=x
            for i in range(self.V):
                if is_negative_cycle[i]:
                    dist[i]=-float('inf')
        if route_restoration:
            return dist,parents
        else:
            return dist

    def Warshall_Floyd(self,route_restoration=False):
        dist=[[float('inf')]*self.V for i in range(self.V)]
        for i in range(self.V):
            dist[i][i]=0
        if route_restoration:
            parents=[[j for j in range(self.V)] for i in range(self.V)]
        for i,j,d in self.edges:
            if dist[i][j]>d:
                dist[i][j]=d
                if route_restoration:
                    parents[i][j]=i
            if not self.directed and dist[j][i]>d:
                dist[j][i]=d
                if route_restoration:
                    parents[j][i]=j
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if dist[i][j]>dist[i][k]+dist[k][j]:
                        dist[i][j]=dist[i][k]+dist[k][j]
                        if route_restoration:
                            parents[i][j]=parents[k][j]
        for i in range(self.V):
            if dist[i][i]<0:
                for j in range(self.V):
                    if dist[i][j]!=float('inf'):
                        dist[i][j]=-float('inf')
        if route_restoration:
            return dist,parents
        else:
            return dist

    def Route_Restoration(self,s,g,parents):
        route=[g]
        while s!=g and parents[g]!=g:
            g=parents[g]
            route.append(g)
        route=route[::-1]
        return route

    def Kruskal(self):
        UF=UnionFind(self.V)
        sorted_edges=sorted(self.edges,key=lambda x:x[2])
        minimum_spnning_tree=[]
        for i,j,d in sorted_edges:
            if not UF.Same(i,j):
                UF.Union(i,j)
                minimum_spnning_tree.append((i,j,d))
        return minimum_spnning_tree

    def Ford_Fulkerson(self,s,t):
        max_flow=0
        residual_graph=[defaultdict(int) for i in range(self.V)]
        if self.weighted:
            for i,j,d in self.edges:
                if not d:
                    continue
                residual_graph[i][j]+=d
                if not self.directed:
                    residual_graph[j][i]+=d
        else:
            for i,j in self.edges:
                residual_graph[i][j]+=1
                if not self.directed:
                    residual_graph[j][i]+=1
        while True:
            parents=[None]*self.V
            parents[s]=s
            seen=[False]*self.V
            seen[s]=True
            queue=deque([s])
            while queue:
                x=queue.popleft()
                for y in residual_graph[x].keys():
                    if not seen[y]:
                        seen[y]=True
                        queue.append(y)
                        parents[y]=x
                        if y==t:
                            tt=t
                            while tt!=s:
                                residual_graph[parents[tt]][tt]-=1
                                residual_graph[tt][parents[tt]]+=1
                                if not residual_graph[parents[tt]][tt]:
                                    residual_graph[parents[tt]].pop(tt)
                                tt=parents[tt]
                            max_flow+=1
                            break
                else:
                    continue
                break
            else:
                break
        return max_flow

    def BFS(self,s):
        seen=[False]*self.V
        seen[s]=True
        queue=deque([s])

        while queue:
            x=queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    y,d=y
                if not seen[y]:
                    seen[y]=True
                    queue.append(y)
                    
        return 

    def DFS(self,s):
        seen=[False]*self.V
        finished=[False]*self.V
        stack=[(s,0)] if self.weighted else [s]

        while stack:
            if self.weighted:
                x,d=stack.pop()
            else:
                x=stack.pop()
            if not seen[x]:
                seen[x]=True
                stack.append((x,d) if self.weighted else x)

                for y in self.graph[x]:
                    if self.weighted:
                        y,d=y
                    if not seen[y]:
                        stack.append((y,d) if self.weighted else y)
            elif not finished[x]:
                finished[x]=True
                
        return 

def Stirling_Second_Numbers(N,K,mod=0):
    stirling_second_numbers=[[0]*(K+1) for i in range(N+1)]
    for n in range(1,N+1):
        stirling_second_numbers[n][1]=1
        for k in range(2,n+1):
            stirling_second_numbers[n][k]=stirling_second_numbers[n-1][k-1]+k*stirling_second_numbers[n-1][k]
            if mod:
                stirling_second_numbers[n][k]%=mod
    return stirling_second_numbers

def Extended_Euclid(n,m):
    stack=[]
    while m:
        stack.append((n,m))
        n,m=m,n%m
    if n>=0:
        x,y=1,0
    else:
        x,y=-1,0
    for i in range(len(stack)-1,-1,-1):
        n,m=stack[i]
        x,y=y,x-(n//m)*y
    return x,y

class MOD:
    def __init__(self,p,e=1):
        self.p=p
        self.e=e
        self.mod=self.p**self.e

    def Pow(self,a,n):
        a%=self.mod
        if n>=0:
            return pow(a,n,self.mod)
        else:
            assert math.gcd(a,self.mod)==1
            x=Extended_Euclid(a,self.mod)[0]
            return pow(x,-n,self.mod)

    def Build_Fact(self,N):
        assert N>=0
        self.factorial=[1]
        self.cnt=[0]*(N+1)
        for i in range(1,N+1):
            ii=i
            self.cnt[i]=self.cnt[i-1]
            while ii%self.p==0:
                ii//=self.p
                self.cnt[i]+=1
            self.factorial.append((self.factorial[-1]*ii)%self.mod)
        self.factorial_inve=[None]*(N+1)
        self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)
        for i in range(N-1,-1,-1):
            ii=i+1
            while ii%self.p==0:
                ii//=self.p
            self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.mod

    def Fact(self,N):
        return self.factorial[N]*pow(self.p,self.cnt[N],self.mod)%self.mod

    def Fact_Inve(self,N):
        if self.cnt[N]:
            return None
        return self.factorial_inve[N]

    def Comb(self,N,K,divisible_count=False):
        if K<0 or K>N:
            return 0
        retu=self.factorial[N]*self.factorial_inve[K]*self.factorial_inve[N-K]%self.mod
        cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]
        if divisible_count:
            return retu,cnt
        else:
            retu*=pow(self.p,cnt,self.mod)
            retu%=self.mod
            return retu

N,M=map(int,readline().split())
W=list(map(int,readline().split()))
mod=10**9+7
MD=MOD(mod)
MD.Build_Fact(10**4)
SSN=Stirling_Second_Numbers(1000,1000,mod=mod)
edges=[]
for _ in range(M):
    i,j=map(int,readline().split())
    i-=1;j-=1
    edges.append((j,i))
ans=0
for s in range(N):
    edges_=[]
    for j,i in edges:
        if W[i]>=W[s] and W[j]>=W[s]:
            edges_.append((j,i))
    G=Graph(N,edges=edges_,directed=True)
    dist=G.SS_BFS(s,unweighted_dist=True)
    for t in range(N):
        if dist[t]!=float('inf'):
            ans+=SSN[W[t]][W[s]]*MD.Fact(W[s])
            ans%=mod
print(ans)
yukicoder

結果

テストケース

ソースコード
