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:
import sys
import numpy as np

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

MOD = 10**9+7
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)
if nY > 0:
    A = np.array(Y, np.int64)
    A %= MOD
    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: Wrong Answer

Solution code:
import sys
import numpy as np

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

MOD = 10*9+7
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)
if nY > 0:
    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: Wrong Answer

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)
if nY > 0:
    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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
from collections import defaultdict
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

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

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

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

memo = [-1]*5001
memo[0] = 1
def fact(n):
    if memo[n] != -1:
        return memo[n]
    else:
        res = n*fact(n-1)%mod
        memo[n] = res
        return res

N = int(input())
P = list(map(int,input().split()))
K = 0
u = UnionFind(N)
loop = 0
for i in range(N):
    if P[i]==-1:
        K += 1
        continue
    if u.find(i)==u.find(P[i]-1):
        loop += 1
    u.union(i,P[i]-1)

d = defaultdict(lambda:[0,0])
for i in range(N):
    if P[i]==-1:
        d[u.find(i)][0] += 1
    d[u.find(i)][1] += 1

n = []
for k in d:
    n.append(d[k])

dp = [[0]*(len(n)+1) for i in range(len(n))]
for i in range(len(n)):
    dp[i][0] = 1
for i in range(len(n)):
    for j in range(1,i+2):
        if j != i+1:
            dp[i][j] += dp[i-1][j]
        dp[i][j] += dp[i-1][j-1]*n[i][0]*n[i][1]
        dp[i][j] %= mod

ans = 0
for i in range(2,len(n)+1):
    if K-i<0:
        break
    ans += dp[len(n)-1][i]*fact(i-1)*pow(N-1,K-i,mod)
    ans %= mod
for i in range(len(n)):
    if K==0:
        break
    ans += n[i][0]*(n[i][1]-1)*pow(N-1,K-1,mod)
    ans %= mod

ans = pow(N-1,K,mod)*(N-loop)-ans
print(ans)

Submission status: Wrong Answer

Solution code:
def productall(a):
    N = len(a)
    if N == 0: return [1]
    A = [1] * N + a[:]
    P = 10 ** 9 + 7
    k = 50
    K = k * 8
    pa1 = (1 << k * 4 + 16) - ((1 << k * 4 + 16) % P)
    pa2 = (1 << k * 2 + 24) - ((1 << k * 2 + 24) % P)
    pa3 = (1 << k + 28) - ((1 << k + 28) % P)
    def modP(x):
        x -= ((x & m1) >> k * 4 + 16) * pa1
        x -= ((x & m2) >> k * 2 + 24) * pa2
        x -= ((x & m3) >> k + 28) * pa3
        return x

    for i in range(N)[::-1]:
        if i == N - 1 or i and 1 << i.bit_length() - 1 == i:
            if i == N - 1:
                c = 2
            else:
                c *= 2
            m1 = int(("1" * (k * 4 - 16) + "0" * (k * 4 + 16)) * c, 2)
            m2 = int(("1" * (k * 6 - 24) + "0" * (k * 2 + 24)) * c, 2)
            m3 = int(("1" * (k * 7 - 28) + "0" * (k + 28)) * c, 2)
        A[i] = modP(A[2*i] * A[2*i+1])

    t = bin(A[1])[2:] + "_"
    return [int(t[-(i+1) * K - 1:-i * K - 1], 2) % P for i in range((len(t)+K-2) // K)]
def par(a):
    L = []
    while P[a] != a:
        L.append(a)
        a = P[a]
    for l in L:
        P[l] = a
    return a
def unite(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb: return
    if LEN[pa] < LEN[pb]:
        a, b, pa, pb = b, a, pb, pa
    P[pb] = pa
    if LEN[pa] == LEN[pb]: LEN[pa] += 1
    CNT[pa] += CNT[pb]
def cnt(a):
    return CNT[par(a)]

N = int(input())
P = [i for i in range(N)]
LEN = [1] * N
CNT = [1] * N
FULL = [0] * N
A = [int(a) - 1 for a in input().split()]
for i, a in enumerate(A):
    if a < 0: continue
    if par(i) != par(a):
        unite(i, a)
    else:
        FULL[i] = 1
for i in range(N):
    if FULL[i]:
        FULL[par(i)] = 1
X = []
Y = []
for i in range(N):
    if par(i) == i:
        if FULL[i] == 0:
            X.append(CNT[i])
        else:
            Y.append(CNT[i])
M = len(X)
mod = 10 ** 9 + 7
ans = (sum(X) + sum(Y) - len(Y)) * pow(N - 1, M, mod) % mod
L = productall([(a << 400) + 1 for a in X])
if M:
    fa = 1
    ans = (ans + M * pow(N - 1, M - 1, mod)) % mod
    for i, l in enumerate(L):
        if i == 0: continue
        ans = (ans - l * fa * pow(N - 1, M - i, mod)) % mod
        fa = fa * i % mod
print(ans)

Submission status: Wrong Answer

Solution code:
def productall(a):
    N = len(a)
    if N == 0: return [1]
    A = [1] * N + a[:]
    P = 10 ** 9 + 7
    k = 20
    K = k * 8
    pa1 = (1 << k * 4 + 16) - ((1 << k * 4 + 16) % P)
    pa2 = (1 << k * 2 + 24) - ((1 << k * 2 + 24) % P)
    pa3 = (1 << k + 28) - ((1 << k + 28) % P)
    def modP(x):
        x -= ((x & m1) >> k * 4 + 16) * pa1
        x -= ((x & m2) >> k * 2 + 24) * pa2
        x -= ((x & m3) >> k + 28) * pa3
        return x

    for i in range(N)[::-1]:
        if i == N - 1 or i and 1 << i.bit_length() - 1 == i:
            if i == N - 1:
                c = 2
            else:
                c *= 2
            m1 = int(("1" * (k * 4 - 16) + "0" * (k * 4 + 16)) * c, 2)
            m2 = int(("1" * (k * 6 - 24) + "0" * (k * 2 + 24)) * c, 2)
            m3 = int(("1" * (k * 7 - 28) + "0" * (k + 28)) * c, 2)
        A[i] = modP(A[2*i] * A[2*i+1])

    t = bin(A[1])[2:] + "_"
    return [int(t[-(i+1) * K - 1:-i * K - 1], 2) % P for i in range((len(t)+K-2) // K)]
def par(a):
    L = []
    while P[a] != a:
        L.append(a)
        a = P[a]
    for l in L:
        P[l] = a
    return a
def unite(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb: return
    if LEN[pa] < LEN[pb]:
        a, b, pa, pb = b, a, pb, pa
    P[pb] = pa
    if LEN[pa] == LEN[pb]: LEN[pa] += 1
    CNT[pa] += CNT[pb]
def cnt(a):
    return CNT[par(a)]

N = int(input())
P = [i for i in range(N)]
LEN = [1] * N
CNT = [1] * N
FULL = [0] * N
A = [int(a) - 1 for a in input().split()]
for i, a in enumerate(A):
    if a < 0: continue
    if par(i) != par(a):
        unite(i, a)
    else:
        FULL[i] = 1
for i in range(N):
    if FULL[i]:
        FULL[par(i)] = 1
X = []
Y = []
for i in range(N):
    if par(i) == i:
        if FULL[i] == 0:
            X.append(CNT[i])
        else:
            Y.append(CNT[i])
M = len(X)
mod = 10 ** 9 + 7
ans = (sum(X) + sum(Y) - len(Y)) * pow(N - 1, M, mod) % mod
L = productall([(a << 160) + 1 for a in X])
if M:
    fa = 1
    ans = (ans + M * pow(N - 1, M - 1, mod)) % mod
    for i, l in enumerate(L):
        if i == 0: continue
        ans = (ans - l * fa * pow(N - 1, M - i, mod)) % mod
        fa = fa * i % mod
print(ans)

Submission status: Wrong Answer

Solution code:
def productall(a):
    N = len(a)
    if N == 0: return [1]
    A = [1] * N + a[:]
    P = 10 ** 9 + 7
    k = 12
    K = k * 8
    pa1 = (1 << k * 4 + 16) - ((1 << k * 4 + 16) % P)
    pa2 = (1 << k * 2 + 24) - ((1 << k * 2 + 24) % P)
    pa3 = (1 << k + 28) - ((1 << k + 28) % P)
    def modP(x):
        x -= ((x & m1) >> k * 4 + 16) * pa1
        x -= ((x & m2) >> k * 2 + 24) * pa2
        x -= ((x & m3) >> k + 28) * pa3
        return x

    for i in range(N)[::-1]:
        if i == N - 1 or i and 1 << i.bit_length() - 1 == i:
            if i == N - 1:
                c = 2
            else:
                c *= 2
            m1 = int(("1" * (k * 4 - 16) + "0" * (k * 4 + 16)) * c, 2)
            m2 = int(("1" * (k * 6 - 24) + "0" * (k * 2 + 24)) * c, 2)
            m3 = int(("1" * (k * 7 - 28) + "0" * (k + 28)) * c, 2)
        A[i] = modP(A[2*i] * A[2*i+1])

    t = bin(A[1])[2:] + "_"
    return [int(t[-(i+1) * K - 1:-i * K - 1], 2) % P for i in range((len(t)+K-2) // K)]
def par(a):
    L = []
    while P[a] != a:
        L.append(a)
        a = P[a]
    for l in L:
        P[l] = a
    return a
def unite(a, b):
    pa = par(a)
    pb = par(b)
    if pa == pb: return
    if LEN[pa] < LEN[pb]:
        a, b, pa, pb = b, a, pb, pa
    P[pb] = pa
    if LEN[pa] == LEN[pb]: LEN[pa] += 1
    CNT[pa] += CNT[pb]
def cnt(a):
    return CNT[par(a)]

N = int(input())
P = [i for i in range(N)]
LEN = [1] * N
CNT = [1] * N
FULL = [0] * N
A = [int(a) - 1 for a in input().split()]
for i, a in enumerate(A):
    if a < 0: continue
    if par(i) != par(a):
        unite(i, a)
    else:
        FULL[i] = 1
for i in range(N):
    if FULL[i]:
        FULL[par(i)] = 1
X = []
Y = []
for i in range(N):
    if par(i) == i:
        if FULL[i] == 0:
            X.append(CNT[i])
        else:
            Y.append(CNT[i])
M = len(X)
mod = 10 ** 9 + 7
ans = (sum(X) + sum(Y) - len(Y)) * pow(N - 1, M, mod) % mod
L = productall([(a << 96) + 1 for a in X])
if M:
    fa = 1
    ans = (ans + M * pow(N - 1, M - 1, mod)) % mod
    for i, l in enumerate(L):
        if i == 0: continue
        ans = (ans - l * fa * pow(N - 1, M - i, mod)) % mod
        fa = fa * i % mod
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


n = int(input())
ppp = list(map(int, input().split()))
MOD = 10 ** 9 + 7
uft = UnionFind(n)
base = 0
undefined = []
for i, p in enumerate(ppp):
    if p == -1:
        undefined.append(i)
        continue
    p -= 1
    if not uft.find(i, p):
        base += 1
        uft.unite(i, p)

if len(undefined) == 0:
    print(base % MOD)
    exit()
elif len(undefined) == 1:
    c = uft.get_size(undefined[0])
    others = n - c
    print((base * (n - 1) + others) % MOD)
    exit()

m = len(undefined)
dp = np.zeros(m + 1, dtype=np.int64)  # 閉路のパターン数
dp[0] = 1
additional = 0  # 閉路を考慮せずに追加される辺数

for i in undefined:
    c = uft.get_size(i)
    dp[1:] += dp[:-1] * c
    dp %= MOD
    additional += n - c

duplicated = 0
pat = pow(n - 1, m, MOD)
inv = pow(n - 1, MOD - 2, MOD)
loop_permutation = 1
loop_other_pattern = pat * inv * inv % MOD
for loop_size in range(2, m + 1):
    duplicated = (duplicated + dp[loop_size] * loop_permutation * loop_other_pattern) % MOD
    loop_other_pattern = loop_other_pattern * inv % MOD
    loop_permutation = loop_permutation * loop_size % MOD

ans = (base * pat + additional * pat * inv - duplicated) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np


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

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


n = int(input())
ppp = list(map(int, input().split()))
MOD = 10 ** 9 + 7
uft = UnionFind(n)
base = 0
undefined = []
for i, p in enumerate(ppp):
    if p == -1:
        undefined.append(i)
        continue
    p -= 1
    if not uft.find(i, p):
        base += 1
        uft.unite(i, p)

if len(undefined) == 0:
    print(base % MOD)
    exit()
elif len(undefined) == 1:
    c = uft.get_size(undefined[0])
    others = n - c
    print((base * (n - 1) + others) % MOD)
    exit()

m = len(undefined)
dp = np.zeros(m + 1, dtype=np.int64)  # 閉路のパターン数
dp[0] = 1
additional = 0  # 閉路を考慮せずに追加される辺数

for i in undefined:
    c = uft.get_size(i)
    dp[1:] += dp[:-1] * c
    additional += n - c

duplicated = 0
pat = pow(n - 1, m, MOD)
inv = pow(n - 1, MOD - 2, MOD)
loop_permutation = 1
loop_other_pattern = pat * inv * inv % MOD
for loop_size in range(2, m + 1):
    duplicated = (duplicated + dp[loop_size] * loop_permutation * loop_other_pattern) % MOD
    loop_other_pattern = loop_other_pattern * inv % MOD
    loop_permutation = loop_permutation * loop_size % MOD

ans = (base * pat + additional * pat * inv - duplicated) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
d = dict()
P = tuple(map(int, input().split()))
for i, p in enumerate(P, 1):
    if p == -1:
        d[i] = 0
target = [0] * (N + 1)
roads = 0
for i, p in enumerate(P, 1):
    if p != -1 and target[p] != i:
        if p in d.keys():
            d[p] += 1
        target[i] = p
        roads += 1
d2 = dict()
for i, (k, v) in enumerate(d.items()):
    d2[k] = N - 1 - v - i
if not d2:
    print(1)
    quit()
K = i + 1
table = [[0] * (K + 1) for _ in range(K + 1)]
table[0][0] = 1
for k in range(K):
    for i, p in enumerate(d2.values()):
        table[i + 1][k] = (table[i + 1][k] + table[i][k] * (N - 1 - p)) % MOD
        table[i + 1][k + 1] += table[i][k] * p
    table[i + 1][k + 1] %= MOD
total = 0
for i in range(K + 1):
    total = (total + (roads + i) * table[K][i]) % MOD
print(total)

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:
                pass

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():
  mod=10**9+7
  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()
  if k==1:
    return ((n-uf.group_count())*(n-1)%mod
            +n-uf.size([i for i,req in enumerate(reqs) if req<0][0]))
print(main())

Submission status: Wrong Answer

Solution code:
import sys

class UFT: #Union-find tree class
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: 
            self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1

mod = 7 + 10 ** 9
def solve():
    input = sys.stdin.readline
    N = int(input())
    P = [int(p) for p in input().split()]
    unknown = P.count(-1)
    totalPatt = pow(N-1, unknown, mod)
    if unknown > 1: addPatt = pow(N-1, unknown - 1, mod)
    else: addPatt = 1
   
    parent = UFT(N)
    ans = 0
    for i, p in enumerate(P):
        if parent.find(i) == parent.find(p-1): continue
        elif p > -1: 
            ans += totalPatt % mod
            ans %= mod
            parent.unite(i, p-1)

    for i, p in enumerate(P):
        if p == -1:
            for j in range(N):
                if parent.find(i) != parent.find(j):
                    #print(i, j, parent.size[j])
                    size = parent.tree.count(parent.find(j))
                    ans += (size * addPatt) % mod
                    ans %= mod
                    parent.unite(i, j)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

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():
  mod=10**9+7
  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()
  if k==1:
    return ((n-uf.group_count())*(n-1)%mod
            +n-uf.size([i for i,req in enumerate(reqs) if req<0][0]))

Submission status: Wrong Answer

Solution code:
def dfs(i):
    stack = [i]
    used[i] = True
    cnt = 1
    is_white = False
    while stack:
        v = stack.pop()
        if p[v] == -1:
            is_white = True
        for nxt_v in graph[v]:
            if used[nxt_v]:
                continue
            stack.append(nxt_v)
            used[nxt_v] = True
            cnt += 1
    return cnt, is_white
     
        
n = int(input())
p = list(map(int, input().split()))
MOD = 10 ** 9 + 7


graph = [set() for i in range(n)]
for a in range(n):
    if p[a] == -1:
        continue
    b = p[a] - 1

    graph[a].add(b)
    graph[b].add(a)

used = [False] * n
white = []
black = []
for i in range(n):
    if not used[i]:
        cnt, is_white = dfs(i)
        if is_white:
            white.append(cnt)
        else:
            black.append(cnt)


# S[i][j] := i個(区別する)をkグループ(区別しない)に分ける場合の数
box = len(white)
ball = len(white)
ru_white = [0] * (len(white) + 1)
for i in range(len(white)):
    ru_white[i + 1] = ru_white[i] + white[i]

S = [[0] * (box + 1) for i in range(ball + 1)]

S[0][0] = 1
for i in range(ball):
    for j in range(box):
        S[i + 1][j + 1] = S[i][j] + S[i][j + 1] * ru_white[j + 1]
        S[i + 1][j + 1] %= MOD

# わかりません
print(sum(S[-1]))