Problem:


Score : 700 points

Problem Statement

There are N towns numbered 1, 2, \cdots, N.

Some roads are planned to be built so that each of them connects two distinct towns bidirectionally. Currently, there are no roads connecting towns.

In the planning of construction, each town chooses one town different from itself and requests the following: roads are built so that the chosen town is reachable from itself using one or more roads.

These requests from the towns are represented by an array P_1, P_2, \cdots, P_N. If P_i = -1, it means that Town i has not chosen the request; if 1 \leq P_i \leq N, it means that Town i has chosen Town P_i.

Let K be the number of towns i such that P_i = -1. There are (N-1)^K ways in which the towns can make the requests. For each way to make requests, find the minimum number of roads needed to meet all the requests, and print the sum of those (N-1)^K numbers, modulo (10^9+7).

Constraints

2 \leq N \leq 5000

P_i = -1 or 1 \leq P_i \leq N.

P_i \neq i

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \cdots P_N

Output

For each way to make requests, find the minimum number of roads needed to meet all the requests, and print the sum of those (N-1)^K numbers, modulo (10^9+7).

Sample Input 1

4
2 1 -1 3

Sample Output 1

8

There are three ways to make requests, as follows:

Choose P_1 = 2, P_2 = 1, P_3 = 1, P_4 = 3. In this case, at least three roads - for example, (1,2),(1,3),(3,4) - are needed to meet the requests.

Choose P_1 = 2, P_2 = 1, P_3 = 2, P_4 = 3. In this case, at least three roads - for example, (1,2),(1,3),(3,4) - are needed to meet the requests.

Choose P_1 = 2, P_2 = 1, P_3 = 4, P_4 = 3. In this case, at least two roads - for example, (1,2),(3,4) - are needed to meet the requests.

Note that it is not mandatory to connect Town i and Town P_i directly.

The sum of the above numbers is 8.

Sample Input 2

2
2 1

Sample Output 2

1

There may be just one fixed way to make requests.

Sample Input 3

10
2 6 9 -1 6 9 -1 -1 -1 -1

Sample Output 3

527841



Sample input:
4
2 1 -1 3


Sample output:
8

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N = int(input())
    P = list(map(int, input().split()))

    # 確定している道でグルーピングする
    uf = UnionFind(N)
    K = 0
    undef = []                  # 要請未完ノードは記録
    for i, p in enumerate(P):
        if p != -1:
            uf.union(i, p-1)
        else:
            K += 1
            undef.append(i)

    # 階乗の事前計算
    factorial = [1]*K
    for i in range(K-1):
        factorial[i+1] = ((i+1)*factorial[i]) % MOD

    # 要請が未完のノードが属するグループサイズをメモ
    size_undef = []
    for i, p in enumerate(P):
        if p == -1:
            size_undef.append(uf.size(p-1))

    # dp[i, j]: i個の根付き木を見てj個を選んだ時の\sum{\prod_v S_v}
    # 「メモリ削減したdpとN^2確保するDP、どっちが早いんやろなあ」
    dp = [[0]*(K+1) for i in range(K+1)]
    dp[0][0] = 1
    for i in range(1, K+1):
        for j in range(i):
            dp_new[j+1] += dp[j]*size_undef[i-1]
        dp = dp_new[:]

    # ただしj=1個を選んだ時のものは特別にsize[i]-1を考える必要がある
    if K >= 1:
        tot = 0
        for s in size_undef:
            tot += s-1
        dp[1] = tot

    # cycleをカウントする
    cycle_count = 0
    for i in range(1, K+1):
        # i個のグループからなるサイクルがひとつできる
        cycle_count += dp[i]*factorial[i-1]*pow(N-1, K-i, MOD)
        cycle_count %= MOD

    # すでに固定サイクルがあれば数える
    cycle_count += (uf.group_count()-K)*pow(N-1, K, MOD)

    # 求めます
    ans = N*pow(N-1, K, MOD) - cycle_count
    ans %= MOD

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
P = list(map(int,input().split()))
from collections import deque
P = [i-1 for i in P]
road = [[] for _ in range(N)]
MOD = 10**9 + 7

plu = 0
for i in range(N):
  if P[i]>=0:
    plu += 1
    road[P[i]].append(i)
    road[i].append(P[i])

    
mi = N - plu
num_pattern = pow(N - 1, mi, MOD)
ans = N * num_pattern
ans %= MOD

flag = [False] * N
num_group = 0
group_list = [-1] * N
for i in range(N):
  if flag[i]:
    continue

  if len(road[i])==0:
    group_list[i] = num_group
    num_group += 1
    flag[i] = True
    
  else:
    q = deque(road[i])
    if flag[i]:
      continue

    flag[i] = True
    group_list[i] = num_group
    while len(q)!=0:
      x = q.popleft()
      if flag[x]:
        continue
      else:
        flag[x] = True
        group_list[x] = num_group
        q = q + deque(road[x])
        
    num_group += 1
    
group_member = [0] * num_group
for i in group_list:
  group_member[i] += 1
  
mi_group = [0] * mi
mi_num = 0
for i in range(10):
  if P[i]>=0:
    continue
  else:
    mi_group[mi_num] = group_member[group_list[i]]
    mi_num += 1

plu_num = num_group - mi_num
dp = [[0] * (mi_num+1) for _ in range(mi_num+1)]
for i in range(mi_num):
  for j in range(i+1):
    dp[i+1][j] += dp[i][j]
    if j>1:
      dp[i+1][j+1] += dp[i][j] * mi_group[i]
    elif j==1:
      dp[i+1][j+1] += (dp[i][j]+i) * mi_group[i]
    else:
      dp[i+1][j+1] += mi_group[i] - 1

l = dp[-1]
factorial = 1
power = [1]*(mi_num+1)
factorial = [1]*(mi_num+1)
for i in range(1,mi_num+1):
  power[i] = power[i-1] * (N-1)
  power[i] %= MOD
  factorial[i] = factorial[i-1]*i
  factorial[i] %= MOD
  

for i in range(1,len(l)):
  ans -= l[i] * factorial[i-1] * power[mi_num-i]
  ans %= MOD
  
ans -= plu_num * power[mi_num]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353
def fft_convolve(f, g, MOD=MOD):
    fft = np.fft.rfft
    ifft = np.fft.irfft
    Lf = f.shape[-1]
    Lg = g.shape[-1]
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1
    fh = f >> 15
    gl = g & (1 << 15) - 1
    gh = g >> 15

    def conv(f, g):
        return ifft(fft(f, fft_len) * fft(g, fft_len))[:, :L]

    x = conv(fl, gl) % MOD
    y = conv(fl + fh, gl + gh) % MOD
    z = conv(fh, gh) % MOD
    a, b, c = map(lambda x: (x + .5).astype(np.int64), [x, y, z])
    return (a + ((b - a - c) << 15) + (c << 30)) % MOD

class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                n_root, child = root, unite_root
            else:
                n_root, child = unite_root, root
            child.parent_ = n_root
            n_root.rank_ = max(n_root.rank_, child.rank_ + 1)
            n_root.member_num_ = n_root.member_num_ + child.member_num_

mod = 10**9+7
NNN = (10**6)
g1 = [1, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
N, = map(int, input().split())
P = list(map(int, input().split()))
K = P.count(-1)

nodes = [UnionFindNode(i) for i in range(N)]
for i, p in enumerate(P):
    p-=1
    if p >= 0:
        nodes[p].unite(nodes[i])

rs = []
X = [0] * N
for i in range(N):
    if nodes[i].is_root():
        rs.append(i)
    if P[i] == -1:
        X[nodes[i].find()] = 1

M = len(rs)
R = N*pow(N-1, K, mod)%mod

Y = []
for i in range(M):
    if X[rs[i]]:
        Y.append(nodes[rs[i]].member_num_)
        R = (R-(nodes[rs[i]].member_num_-1)*pow(N-1, K-1, mod))%mod
    else:
        R = (R-pow(N-1, K, mod))%mod
nY = len(Y)
A = np.array(Y, np.int64)
polys = np.empty((nY, 2), np.int64)
polys[:, 1] = 1
polys[:, 0] = A

while len(polys) > 1:
    if len(polys) & 1:
        polys = np.pad(polys, ((0, 1), (0, 0)))
        polys[-1, 0] = 1
    P = polys[:len(polys) // 2]
    Q = polys[len(polys) // 2:]
    polys = fft_convolve(P, Q)

P = polys[0]
for i in range(nY):
    if nY-i == 1:
        continue
    R -= pow(N-1, K-(nY-i), mod) * g1[nY-i-1] * P[i]
    R %= mod
print(R)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
K = A.count(-1)
pointed = {i : 0 for i in range(1, N+1)}
for i, elt in enumerate(A):
    if elt != -1:
        pointed[elt] += 1

ans = 0
for i, elt in enumerate(A):
    if elt != -1:
        if A[elt-1] == i+1:
            ans += (N-1)**K/2
        elif A[elt-1] != -1:
            ans += (N-1)**K
        else:
            ans += (N-1)**K-(N-1)**(K-1)/2
    else:

        ans += (N-1)**(K-1)*(pointed[i+1]/2+N-K-pointed[i+1]+(K-1)*(N-1.5)/(N-1))

print(int(ans)%(10**9+7))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
K = A.count(-1)
pointed = {i : 0 for i in range(1, N+1)}
for i, elt in enumerate(A):
    if elt != -1:
        pointed[elt] += 1

ans = 0
for i, elt in enumerate(A):
    if elt != -1:
        if A[elt-1] == i+1:
            ans += (N-1)**K/2
        elif A[elt-1] != -1:
            ans += (N-1)**K
        else:
            ans += (N-1)**K-(N-1)**(K-1)/2
    else:

        ans += (N-1)**(K-1)*(pointed[i+1]/2+N-K-pointed[i+1]+(K-1)*(N-1.5)/(N-1))

print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
N = int(input())
nums = input().split()
nums = [int(s) for s in nums]
indexes = []
result = 0

def calc_result(result,indexes):
  if len(indexes) == 0:
    return 0
  index = indexes[0]
  for j in range(N-1):
    J = j + 1
    s = set()
    if index+1 < J:
      s.add(str(index+1) + str(J))
    elif J < index+1:
      s.add(str(J) + str(index+1))
    else:
      pass
    for k in range(N):
      if nums[k] != -1:
        if k+1 < nums[k]:
          s.add(str(k+1) + str(nums[k]))
        else:
          s.add(str(nums[k]) + str(k+1))
    try:
      indexes.pop(0)
    except:
      pass
    print("indexes:{}, result:{}, s{}".format(indexes,result,s))
    result = result + len(s) + calc_result(result,indexes)
  return result

for i in range(N):
  if nums[i] == -1:
    indexes.append(i)
if len(indexes) != 0:
  result = calc_result(result, indexes)
else:
  for j in range(N-1):
      J = j + 1
      s = set()
      for k in range(N):
        if nums[k] != -1:
          if k+1 < nums[k]:
            s.add(str(k+1) + str(nums[k]))
          else:
            s.add(str(nums[k]) + str(k+1))
      result = result + len(s)
print(result%((10**9)+7))

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class UF(object):
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
        self.size = [1]*n

    # x が属する集合の代表値を返す
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = y = self.find(self.par[x])
            return y

    # x と y の集合を結合する
    def union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                px, py = py, px
            if self.rank[px] == self.rank[py]:
                self.rank[px] += 1
            self.par[py] = px
            self.size[px] += self.size[py]
            return

    # x と y が同じ集合に属するか判定する
    def is_same(self,x,y):
        return self.find(x) == self.find(y)

    # x が属する集合の要素数を返す
    def get_size(self,x):
        return self.size[self.find(x)]

N = I()
P = LI()

K = 0

uf = UF(N)
for i in range(N):
    if P[i] != -1:
        uf.union(i,P[i]-1)
    else:
        K += 1

l = defaultdict(int)
m = defaultdict(int)

for i in range(N):
    p = uf.find(i)
    l[p] += 1
    if P[i] == -1:
        m[p] += 1

# beki[i][j] : i^j
beki = [[1]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if j == 0:
            continue
        else:
            beki[i][j] = beki[i][j-1]*i
            beki[i][j] %= mod

ans = 0
for i in l.keys():
    ans += uf.get_size(i)-1

for i in range(N):
    for j in range(i+1,N):
        if uf.is_same(i,j):
            continue
        count = beki[N-1][K]-beki[N-1-l[i]][m[j]]*beki[N-1-l[j]][m[i]]
        count %= mod
        ans += count
        ans %= mod
        
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))

node_max = [1]
for i in range(1, n+1):
    node_max.append(min(10**18, node_max[i-1]*2-a[i]))

a.reverse()
node_max.reverse()

node_max
ans = 0
main = 0
node_max.append(0)


flag = 1

for i in range(n+1):
    main = min(main+a[i], node_max[i+1])
    ans += main + a[i]
    if i == 0:
        continue
    if (main+a[i]) > node_max[i+1]*2:
        flag = 0
        break


if flag == 1:
    print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(m):
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
ans=0
for v in range(1,n+1):
 for u in g[v]: #i番目の展望台から1本の道を通っていけるすべての展望台と高さを比較する
   if arr[u]>=arr[v]:
     break
 else: #i番目の展望台の高さが他のすべての展望台の高さより真に大きければ答えを1増やす
   ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
#from collections import deque
import sys 
sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

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

# = [list(map(int,input().split())) for _ in range(XXXX)]




def saiki(d,point,counter):
    counter += point
    if d == n:
        if point == a[n]:
            print(counter)
            exit()
        else:
            return
    
    if point-a[d] <= 0:
        #すべて葉 or 葉の数がa[d]に足りない。
        return

    for nextp in range((point-a[d])*2,point-a[d]-1,-1):
        saiki(d+1,nextp,counter)
    
    return


def main():
    saiki(0,1,0)
    print(-1)


if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    main()

Submission status: Runtime Error

Solution code:
#from pprint import pprint
#from collections import defaultdict
#from collections import Counter
#from copy import deepcopy
#from itertools
from collections import deque
import sys 
sys.setrecursionlimit(10**8) #N回まで再起を許可する。

# = map(int,input().split())

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

# = [list(map(int,input().split())) for _ in range(XXXX)]




def saiki(d,point,counter):
    counter += point
    if d == n:
        if point == a[n]:
            print(counter)
            exit()
        else:
            return
    
    if point-a[d] <= 0:
        #すべて葉 or 葉の数がa[d]に足りない。
        return

    for nextp in range((point-a[d])*2,point-a[d]-1,-1):
        saiki(d+1,nextp,counter)
    
    return








n = int(input())
a = list(map(int,input().split()))


saiki(0,1,0)

print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    f = [0 for i in range(N)]
    f[0] = 1
    count = sum(A) - 1
    upper = sum([2 ** i for i in range(N)])
    if sum(A) > upper:
        print('-1')
        return
    for d in range(1, N):
        f[d] = 2 * min(f[d-1], count) - A[d] + min(max(f[d-1]-count, 0), f[d-1])
        count -= min(f[d-1], count)
    print(sum(f)+sum(A))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N - 0 + 1)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
a