提出 #36438357

---

ソースコード 拡げる

mod=998244353

M=(10**5)*3+1 
fac=[1]*M
ninv=[1]*M
finv=[1]*M
for i in range(2,M):
  fac[i]=fac[i-1]*i%mod
  ninv[i]=(-(mod//i)*ninv[mod%i])%mod
  finv[i]=finv[i-1]*ninv[i]%mod

def binom(n,k):
  if n<0 or k<0:
    return 0
  if k>n:
    return 0
  return (fac[n]*finv[k]%mod)*finv[n-k]%mod

from sys import stdin
input=lambda :stdin.readline()[:-1]

n,m,k=map(int,input().split())
edge=[[] for i in range(n)]
for _ in range(m):
  v,u=map(lambda x:int(x)-1,input().split())
  edge[v].append(u)
  edge[u].append(v)

c=list(map(int,input().split()))

ans=0
dp0=[0]*n
dp1=[0]*n
dp2=[0]*n
dp0[0]=1

for _ in range(k):
  ndp0=[0]*n
  ndp1=[0]*n
  ndp2=[0]*n
  
  for i in range(n):
    s=len(edge[i])
    for to in edge[i]:
      ndp0[to]+=dp0[i]*ninv[s]
      ndp1[to]+=dp1[i]*ninv[s]
      ndp2[to]+=dp2[i]*ninv[s]
  
  for i in range(n):
    ndp0[i]%=mod
    ndp1[i]%=mod
    ndp2[i]%=mod
    if c[i]==0:
      ndp2[i]+=2*ndp1[i]+ndp0[i]
      ndp2[i]%=mod
      ndp1[i]+=ndp0[i]
      ndp1[i]%=mod
    else:
      ans+=ndp2[i]
      ans%=mod
  
  dp0=ndp0
  dp1=ndp1
  dp2=ndp2
  #print(dp0,dp1,dp2)

print(ans%mod)

提出情報

ジャッジ結果