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: Wrong Answer

Solution code:
from sys import stdin
from collections import deque
input = stdin.readline

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

bridge = [set([]) for _ in range(N)]
mod = 10 ** 9 + 7


def bfs(start, goal):
    q = deque([])

    seen[start] = 1
    q.append(start)

    while q:
        now = q.popleft()

        for nex in bridge[now]:
            seen[nex] = 1

            if nex == i:
                return
            else:
                q.append(nex)


K = 0

for i in range(N):
    if P[i] == -1:
        K += 1
        continue
    else:
        seen = [0] * N
        bfs(i, P[i] - 1)
        # すでにつながっているならOK, そうでないなら橋を追加
        if not seen[P[i] - 1]:
            bridge[i].add(P[i] - 1)
            bridge[P[i] - 1].add(i)

connections = [0] * N

for i in range(N):
    seen = [0] * N
    bfs(i, -1)
    connections[i] = sum(seen) - 1

# print(bridge)
# print(connections)

base = 0

for b in bridge:
    base += len(b)

base //= 2

if not (-1) in P:
    print(base)
    exit()

ans = (base + K) * pow(N - 1, K, mod)
ans %= mod

for i in range(N):
    for j in range(N):
        if P[i] == -1 and P[j] == -1:
            if i == j:
                ans -= connections[i]
            else:
                ans -= connections[i]

print(ans)

Submission status: Wrong Answer

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
l=[-1]+L()
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
uf=unionfind(n)
d=[]
for i in range(1,n+1):
    if l[i]==-1:
        d.append(i)
    else:
        uf.unite(i,l[i])
d1=0
mod=10**9+7
k=len(d)
for i in d:
    if uf.count(i)==1:
        d1+=1
ans=pow(n-1,k+1,mod)

for i,j in enumerate(d):
    tmp=uf.count(j)
    if tmp==1:
        pass
    else:
        ans-=(tmp-1)*pow(n-tmp-1,k-1,mod)
        ans%=mod

N=n
fac=[1]*(N+3)
inv=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+2],mod-2,mod)
for i in range(N+2,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    if r>n or r<0:
        return 0
    return fac[n]*inv[n-r]*inv[r]%mod

if d1>=2:
    for i in range(2,d1+1):
        x=comb(d1,i)*pow(n-1-i,k-i,mod)*fac[i-1]
        ans-=x
        ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
import unittest


class UnionFind:

    def __init__(self, size: int):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.parent = [-1] * size

    def find(self, x: int) -> int:
        """
        xを含む集合の代表を求める
        """
        if self.parent[x] < 0:
            return x
        # 集合の代表にリンクを繋ぎ変える
        same_group_items = []
        while self.parent[x] >= 0:
            same_group_items.append(x)
            x = self.parent[x]
        for child in same_group_items:
            self.parent[child] = x
        return x

    def unite(self, x: int, y: int):
        """
        xを含む集合とyを含む集合を併合する
        """
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.parent[root_x] >= self.parent[root_y]:
                self.parent[root_x] += self.parent[root_y]
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] += self.parent[root_x]
                self.parent[root_x] = root_y

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def count_group(self) -> int:
        """
        集合の数を数える。
        """
        count = 0
        for i in range(self.size):
            if self.parent[i] < 0:
                count += 1
        return count

    def get_size(self, x):
        return -1 * self.parent[self.find(x)]


def solve(n, ps):
    mod = 10**9+7
    undefs = []
    uf = UnionFind(n)
    base_cost = 0
    for i in range(n):
        if ps[i] == -1:
            undefs.append(i)
        else:
            p = ps[i]-1
            if not uf.same(p, i):
                base_cost += 1
                uf.unite(p, i)
    n_undef = len(undefs)
    n_undef_pattern_p = pow(n - 1, n_undef-2, mod)
    n_undef_pattern = n_undef_pattern_p*(n-1)*(n-1) % mod
    base_cost = base_cost * n_undef_pattern

    cost = 0
    for i, p in enumerate(undefs):
        m = uf.get_size(p)-1
        cost += (n - 1 - m) * n_undef_pattern_p * (n - 1)
        cost -= i * n_undef_pattern_p * (n - 2)
        cost %= mod

    # print(base_cost, cost, n_undef, n_undef_pattern)

    return (base_cost + cost) % mod


def main():
    n = int(input())
    ps = list(map(int, input().split()))
    result = solve(n, ps)
    print(result)


class Test(unittest.TestCase):
    def test_solve_1(self):
        n = 4
        p = [2, 1, -1, 3]
        actual = solve(n, p)
        expected = 8
        self.assertEqual(actual, expected)

    def test_solve_2(self):
        n = 2
        p = [2, 1]
        actual = solve(n, p)
        expected = 1
        self.assertEqual(actual, expected)

    def test_solve_3(self):
        n = 10
        p = [2, 6, 9, -1, 6, 9, -1, -1, -1, -1]
        actual = solve(n, p)
        expected = 527841
        self.assertEqual(actual, expected)

    def test_solve_4(self):
        n = 2
        p = [2, -1]
        actual = solve(n, p)
        expected = 1
        self.assertEqual(actual, expected)

    def test_solve_5(self):
        n = 2
        p = [-1, -1]
        actual = solve(n, p)
        expected = 1
        self.assertEqual(actual, expected)

    def test_solve_6(self):
        n = 3
        p = [-1, -1, -1]
        actual = solve(n, p)
        expected = 16
        self.assertEqual(actual, expected)

    def test_solve_7(self):
        n = 4
        p = [-1, -1, -1, -1]
        actual = solve(n, p)
        expected = 240
        self.assertEqual(actual, expected)

    def test_solve_8(self):
        n = 4
        p = [2, -1, -1, -1]
        actual = solve(n, p)
        expected = 80
        self.assertEqual(actual, expected)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod=10**9+7

def modInv(x, m=mod):
    return pow(x, m - 2, m) % m

def modDiv(x, y, m=mod):
    return x * modInv(y, m) % m

def modnCr(n, r, m=mod):
    if n==0:
        return 0
    if r > n - r:
        r = n - r
    denom = 1
    numer = 1
    for i in range(r):
        denom = (n - i) * denom % m
        numer = (i + 1) * numer % m
    return modInv(numer, m) * denom % m

n = int(input().strip())
L = list(map(int, input().strip().split()))
to=[set() for _ in range(n)]
default=0
k=0
for i,v in enumerate(L):
    if v==-1:
        k+=1
        continue
    if v-1 not in to[i]:
        default+=1
    to[i].add(v-1)
    to[v-1].add(i)
already=0
for i in range(n):
    if L[i]==-1:
        already+=len(to[i])

ans=(default+k)*pow(n-1,k,mod)%mod
if k:
    ans-=pow((already+modnCr(k,2))*(n-1)%mod,k-1,mod)
print(ans%mod)

Submission status: Wrong Answer

Solution code:
def main():

    N = int(input())
    P = list(map(int, input().split()))
    mod = pow(10, 9) + 7

    a = set()
    for i in range(N):
        if P[i] != -1:
            if i < P[i]-1:
                a.add((i, P[i]-1))
            else:
                a.add((P[i]-1, i))
    l = len(a) % mod

    if -1 not in P:
        return l

    parent = [i for i in range(N)]
    def find(parent, i):
        if i != parent[i]:
            parent[i] = find(parent, parent[i])
        return parent[i]

    def union(parent, i, j):
        pi, pj = find(parent, i), find(parent, j)
        if pi != pj:
            parent[pi] = pj

    for i in range(N):
        if P[i] != -1:
            union(parent, i, P[i]-1)

    for i in range(N): find(parent, i)

    ans = 0
    for i in range(N):
        if P[i] == -1:
            for j in range(N):
                if j != i:
                    if parent[i] != parent[j]:
                        ans += l + 1
                    else:
                        ans += l
                    ans %= mod
    return ans





if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict


def read():
    N = int(input().strip())
    P = list(map(int, input().strip().split()))
    return N, P


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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


def binom_preprocess(n, MOD=10**9+7):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % MOD
        invf[i] = pow(f[i], MOD-2, MOD)
    return f, invf


def binom(n, k, f, invf, MOD=10**9+7):
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % MOD) * invf[n-k] % MOD


def solve(N, P, MOD=10**9+7):
    uf = UnionFind(N)
    for i in range(N):
        if P[i] > 0:
            uf.union(i, P[i]-1)
    roots = uf.roots()

    rd = dict()
    for r in roots:
        rd[r] = True  # group is fixed
    rd_count = sum([1 for r in rd.values() if r])
    
    for i in range(N):
        if P[i] < 0:
            r = uf.find(i)
            rd[r] = False  # group is frexible

    n_groups = len(roots)
    min_paths = [uf.size(g) - 1 for g in roots]
    min_paths_sum = sum(min_paths)

    ans = 0
    f, invf = binom_preprocess(N+N)

    for k in range(0, n_groups):
        p = binom(N, k, f, invf) * (min_paths_sum + k) % MOD
        ans += p
        ans %= MOD
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

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 = plu * 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
  
for i in range(N):
  if P[i]>=0:
    continue
  else:
    x = N - group_member[group_list[i]]
    ans += x * pow(N-1,mi-1,MOD)
    ans %= MOD
    
print(ans)

Submission status: Wrong Answer

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


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

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

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

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

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

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


def main():
    MOD = 10 ** 9 + 7

    N = int(input())
    P = (int(x) - 1 for x in input().split())

    uf = UnionFind(N)

    qs = []
    not_built = [[1] * N for _ in range(N)]
    e = 0
    for v, u in enumerate(P):
        if u == -2:
            qs.append(u)
        else:
            uf.unite(v, u)
            if v > u:
                v, u = u, v
            if not_built[v][u]:
                not_built[v][u] = 0
                e += 1

    ans = e * pow(N - 1, len(qs), MOD) % MOD
    if qs:
        cl = Calc(max_value=len(qs) * 2, mod=MOD)
        t = 0
        for q in qs:
            t = ((t + 1) * (N - uf.size(q)) + t * uf.size(q)) % MOD # ?????
        # for use_in_group in range(2, len(qs) + 1):
        #     for k in range(2, use_in_group + 1):
        #         t -= k * cl.nHr(use_in_group, k) * pow(N - 1 - use_in_group, len(qs) - use_in_group, MOD) % MOD
        ans = (ans + t) % MOD
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
P = list(map(int, input().split()))


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


def modpow(x, n, mod):
    ret = 1
    for i in range(n):
        ret *= x
        ret %= mod
    return(ret)


mod = 10**9 + 7

L = []
G = unionFind(N)
for i in range(N):
    if P[i] == -1:
        L.append(i)
    else:
        P[i] -= 1
        G.unite(P[i], i)
K = len(L)
for i in range(N):
    G.root(i)
d = collections.Counter(G.parent)
s = 0  # グループごとの道の数
for x in d:
    s += d[x] - 1


ans = s * modpow(N-1, K, mod)

#cost = [[0]*K for i in range(N)]
dp = [[0 for i in range(N)] for i in range(N)]
for ii, i in enumerate(L):
    a = modpow(N-1, K-1-ii, mod)
    for j in range(N):
        if i == j:
            continue
        else:
            if G.same(i, j):
                continue
            else:
                dp[i][j] = a
                for k in L:
                    if k >= i:
                        break
                    else:
                        dp[i][j] -= dp[i][k] * dp[k][j]
                dp[i][j] %= mod
    ans += sum(dp[i])
    ans %= mod
# print(dp)
print(ans)

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    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 same(self, x, y):
        return self.find(x) == self.find(y)

    def sum(self):
        return sum(-x - 1 for x in self.parents if x < 0)


MOD = 10 ** 9 + 7

N = int(input())
D = DisjointSet(N)
P = list(map(lambda x: int(x) - 1, input().split()))
for i in range(N):
    if P[i] >= 0:
        D.union(i, P[i])
sum_D = D.sum()
ans = 1
for i in range(N):
    tmp = 0
    if P[i] >= 0:
        continue
    for j in range(N):
        if i == j:
            continue
        if D.same(i, j):
            tmp += sum_D
        else:
            tmp += sum_D + 1
    ans *= tmp
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
P_list = list(map(int, input().split()))

class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, node):
		parent = self.groups[node]
		if parent == node:
			return parent
		else:
			root = parent
			parent = self.groups[parent]
			while root != parent:
				root = parent
				parent = self.groups[parent]
			
			while node != root:
				tmp = self.groups[node]
				self.groups[node] = root
				node = tmp
			
			return root
	
	def set_root(self, node, root):
		parent = self.groups[node]
		while parent != root:
			self.groups[node] = root
			node = parent
			parent = self.groups[node]
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_counts(self):
		table = [None] * len(self.groups)
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if table[g] != None:
				table[g] += 1
			else:
				table[g] = 1
		
		for i in range(len(self.groups)):
			table[i] = table[self.get_root(i)]
		
		return table

	def to_list_list(self):
		table = [[] for _ in range(len(self.groups))]
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if table[g] != None:
				table[g].append(i)
			else:
				table[g] = [i]
		
		for i in range(len(self.groups)):
			table[i] = table[self.get_root(i)]
		
		return table
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].append(i)
			else:
				table[g] = [i]
		return table
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]

uf = UnionFind(N)
not_decided = set()
for i, p in enumerate(P_list):
	if p >= 1:
		p -= 1
		uf.combine(i, p)
	else:
		not_decided.add(i)

total_bridges = 0
groups = uf.to_list()
not_decided_counts = []
for group in groups:
	count = 0
	for i in group:
		if i in not_decided:
			count += 1
	not_decided_counts.append(count)
	total_bridges += len(group) - 1

#print(groups)
#print(not_decided_counts)
#print(total_bridges)

M = 10 ** 9 + 7

not_decided_count = len(not_decided)
total = ((total_bridges + not_decided_count) * pow(N - 1, not_decided_count, M)) % M
for i in range(len(groups)):
	g1 = groups[i]
	c1 = not_decided_counts[i]
	if c1 > 0:
		l1 = len(g1)
		total = (total - (l1 - 1) * pow(N - 1, not_decided_count - c1, M)) % M
		for j in range(i + 1, len(groups)):
			g2 = groups[j]
			c2 = not_decided_counts[j]
			if c2 > 0:
				l2 = len(g2)
#				print(not_decided_count, c1, c2)
				total = (total - (l1 * l2) * pow(N - 1, not_decided_count - c1 - c2, M)) % M

print(total)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import copy

n = int(input())
p = list(map(int, input().split()))
p.insert(0, 0)
mati = [i for i in range(1, n+1)]
g = [[] for _ in range(n+1)]#隣接リスト
cnt = 0
mod = 10 ** 9 + 7

for j in permutations(mati, p.count(-1)):
    p2 = copy.deepcopy(p)
    g = [[] for _ in range(n+1)]#隣接リスト
    flg = False
    for k in range(p.count(-1)):
        if p2.index(-1) == j[k]:
            flg = True
            break
        p2[p2.index(-1)] = j[k]
    if flg:
        continue
    for i in range(1, n+1):
        if (p2[i], i) in g[p2[i]]:
            continue
        g[i].append((i, p2[i]))
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = input()
k = p.count('-1')
r = [int(s) for s in p.split(' ')]

tnum = 0
ans = 0
requests = []
req = ''

for i, v in enumerate(r):
    #init
    tnum = i + 1
    req = ''
    
    #create order
    if tnum == v:
        pass
    else:
        if tnum < v:
            req = '{0} to {1}'.format(tnum, v)
        elif tnum > v:
            req = '{0} to {1}'.format(v, tnum)
        
        #set request
        if req not in requests:
            requests.append(req)
        

#print(requests)
ans = len(requests) % (10^9+7)

print(ans)

Submission status: Wrong Answer

Solution code:

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

frag=list(range(n+2))
fragnum=[0]*(n+2)

hatena=[]

mod=10**9+7

#以下でフラグ建設 フラグが同じなら同じチームである
def takefrag(p):
    stock=[]
    while frag[frag[p]]!=frag[p]:
        stock.append(p)
        p=frag[p]
    p=frag[p]
    for i in stock:
        frag[i]=p
    return p
for a,b in enumerate(A):
    if b==-1:
        hatena.append(a+1)
        continue
    a+=1
    a,b = map(takefrag,(a,b))
    a,b = min(a,b),max(a,b)
    frag[a]=b
for i in range(n+1):
    frag[i]=takefrag(i)
    fragnum[frag[i]]+=1

ans=0
for i in fragnum[1:-1]:
    ans+=max(0,i-1)

k=len(hatena)
ans*=pow(n-1,k,mod)
ans%=mod

num=0
for h in hatena:
    k-=1
    h=takefrag(h)
    num+=fragnum[h]
    tmp=n-num
    tmp*=pow(n-1,k,mod)
    tmp%=mod
    ans+=tmp
    ans%=mod
    
print(ans)

Submission status: Wrong Answer

Solution code:

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

frag=list(range(n+2))
fragnum=[0]*(n+2)

hatena=[]

mod=10**9+7

#以下でフラグ建設 フラグが同じなら同じチームである
def takefrag(p):
    stock=[]
    while frag[frag[p]]!=frag[p]:
        stock.append(p)
        p=frag[p]
    p=frag[p]
    for i in stock:
        frag[i]=p
    return p
for a,b in enumerate(A):
    if b==-1:
        hatena.append(a)
        continue
    a+=1
    a,b = map(takefrag,(a,b))
    a,b = min(a,b),max(a,b)
    frag[a]=b
for i in range(n+1):
    frag[i]=takefrag(i)
    fragnum[frag[i]]+=1

ans=0
for i in fragnum[1:-1]:
    ans+=max(0,i-1)

k=len(hatena)
ans*=pow(n-1,k,mod)
ans%=mod

num=0
for h in hatena:
    k-=1
    h=takefrag(h)
    num+=fragnum[h]
    tmp=n-num
    tmp*=pow(n-1,k,mod)
    tmp%=mod
    ans+=tmp
    ans%=mod
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = input(int())
A = list(map(int, input().split()))

count = 0
B4 = 0

for i in A:
    count += i + 1

print(count)

Submission status: Wrong Answer

Solution code:
N = input(int())
A = list(map(int, input().split()))

count = 0
B3 = 0

for i in A:
    count += i + 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))

if A[0] != 0 or A[N] == 0:
    print(-1)
else:
    B = [0]*(N+1)
    C = [0]*(N+1)
    B[0] = 1
    C[N] = A[N]
    for i in range(1,N+1):
        B[i] = (B[i-1]-A[i-1]) * 2
        C[N-i] = C[N+1-i]+A[N-i]
    sum = 0
    flag = True
    for i in range(0,N+1):
        sol = min(B[i],C[i])
        if (i < N and sol <= A[i]) or (i == N and sol < A[i]): 
            flag = False
            break
        sum += sol
    if flag == True:
        print(sum)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
N = input(int())
A = list(map(int, input().split()))

count = 0
B2 = 0

for i in A:
    count += i + 1

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = list(map(int, input().split()))
NUM = 10**9 + 7

for i in range(len(P)):
    P[i] -= 1

#基本的な道の数
#既知→未知の道の数
base = N
cnt = 0
k_unk_num = 0
for i, value in enumerate(P):
    if value >= 0:
        if P[value] == i:
            cnt += 1
        elif P[value] == -2:
            k_unk_num += 1
base -= cnt // 2

#未知の道の数
unknown_num = 0
for i in P:
    if i < 0:
        unknown_num += 1

# print(base, unknown_num, k_unk_num)

ans = 0
ans = (ans + base * (N-1) ** unknown_num) % NUM
# print(ans)
ans = int(ans - k_unk_num * (N-1) ** (unknown_num-1) + NUM) % NUM
# print(ans)
if unknown_num > 1:
    ans = (ans - (unknown_num * (unknown_num-1) // 2) * (N-1) ** (unknown_num-2) + NUM) % NUM

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

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

a_b = {i:set() for i in range(N)}
b_a = {}
a_1 = deque()
for i, p in enumerate(P):
  if p == -1:
    a_1.append(i)
  else:
    j = p - 1
    if i in b_a:
      i = b_a[i]
    if j in b_a:
      j = b_a[j]
    if i == j:
      continue
    if i > j:
      i, j = j, i

    for k in a_b[j]:
      b_a[k] = i
    b_a[j] = i
    a_b[i] |= a_b[j]
    a_b[i].add(j)
    del a_b[j]

print(a_b)
print(b_a)

ans = 0
que = deque()
que.append((a_b, b_a, a_1, 1))
while que:
  a_b, b_a, a_1, dup = que.pop()
  if a_1:
    a_1 = a_1.copy()
    i = a_1.popleft()
    if i in b_a:
      i = b_a[i]
    for j in a_b.keys():
      if i == j and len(a_b[j]) == 0:
        continue
      a_b2 = {k:v.copy() for k, v in a_b.items()}
      b_a2 = b_a.copy()
      if (i == j) or (i in a_b[j]):
        dup2 = dup * len(a_b[j])
      else:
        dup2 = dup * (len(a_b[j]) + 1)

      ii, jj = i, j
      if ii != jj:
        if ii > jj:
          ii, jj = jj, ii

        for k in a_b2[jj]:
          b_a2[k] = ii
        b_a2[jj] = ii
        a_b2[ii] |= a_b2[jj]
        a_b2[ii].add(jj)
        del a_b2[jj]

      que.append((a_b2, b_a2, a_1, dup2))
  else:
    ans += sum(len(a_b[x]) for x in a_b) * dup

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD = 10**9 + 7

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

dict = [ [0 for j in range(N+1)] for i in range(N+1)]
cnt = 0
m = 0

for i in range(N):
  a = List[i]
  if a == -1:
    dict[i+1] = 0
    m+=1

for i in range(N):
  a = List[i]
  if a != -1:
    if type(dict[a]) != int :
      if dict[a][i+1] == 0:
        dict[a][i+1] = 1
        dict[i+1][a] = 1
        cnt += 1
        
    else:
      dict[i+1][a] = 1
      dict[a] += 1
      cnt += 1
      

ans = 1
for i in range(N+1):
  a = dict[i]
  if type(a) == int:
    ans += ( (cnt) * ((N-1)**m) + (N-1-a)*((N-1)**(m-1)) ) % MOD

if ans == 0:
  print(1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
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())
  reqs=list(map(int,input().split()))
  reqs=[req-1 for req in reqs]
  uf=UnionFind(n)
  k=0
  for i,req in enumerate(reqs):
    if req>=0:
      uf.union(i,req)
    else:
      k+=1
  if k==0:
    return n-uf.group_count()

print(main())

Submission status: Wrong Answer

Solution code:
N=int(input())
P=list(map(int, input().split()))
par=[i for i in range(N)]
rank=[0]*(N)
size=[1]*N
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

#同じ集合か判定
def same(x,y):
  return find(x)==find(y)

def union(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 
  if rank[x]>rank[y]:
    par[y]=x
    size[x]+=size[y]
  else:
    par[x]=y
    size[y]+=size[x]
    if rank[x]==rank[y]:
      rank[y]+=1

for i in range(N):
  union(P[i]-1,i) 
      
d=P.count(-1)
mod=10**9+7
f=0
SI=list(set(par))
for i in SI:
  e=size[i]
  f+=(e*(e-1)//2)
ans=(pow(N-d,d,mod))*f
ans%=mod
pl=0
for i in range(N):
  if P[i]==-1:
    pl+=N-size[par[i]]
pl%=mod
print((ans+pl)%mod)