Problem:


Score : 1000 points

Problem Statement

There are N towns in Takahashi Kingdom. They are conveniently numbered 1 through N.

Takahashi the king is planning to go on a tour of inspection for M days. He will determine a sequence of towns c, and visit town c_i on the i-th day. That is, on the i-th day, he will travel from his current location to town c_i. If he is already at town c_i, he will stay at that town. His location just before the beginning of the tour is town 1, the capital. The tour ends at town c_M, without getting back to the capital. 

The problem is that there is no paved road in this kingdom. He decided to resolve this issue by paving the road himself while traveling. When he travels from town a to town b, there will be a newly paved one-way road from town a to town b.

Since he cares for his people, he wants the following condition to be satisfied after his tour is over: "it is possible to travel from any town to any other town by traversing roads paved by him". How many sequences of towns c satisfy this condition?

Constraints

2≦N≦300

1≦M≦300

Input

The input is given from Standard Input in the following format:

N M

Output

Print the number of sequences of towns satisfying the condition, modulo 1000000007 (=10^9+7).

Sample Input 1

3 3

Sample Output 1

2

As shown below, the condition is satisfied only when c = (2,3,1) or c = (3,2,1). Sequences such as c = (2,3,2), c = (2,1,3), c = (1,2,2) do not satisfy the condition.

Sample Input 2

150 300

Sample Output 2

734286322

Sample Input 3

300 150

Sample Output 3

0



Sample input:
3 3


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9+7

N,M = map(int,read().split())

"""
・既に強連結成分として確定している町の個数
・訪問済だけれど強連結成分には入っていない町の個数
に対する場合の数を持ってdp
"""

dp = np.zeros((N+1,N+1),np.int64)
dp[1,0] = 1

rng = np.arange(N+1,dtype=np.int64)

for _ in range(M):
    prev = dp
    dp = np.zeros_like(prev)
    # 強連結成分から出発する場合。
    dp[:,0] += prev[:,0] * rng
    dp[:,1] += prev[:,0] * rng[::-1]
    # 未確定部分から
    for m in range(1,N):
        # 強連結成分に戻る
        dp[m:,0] += prev[:-m,m] * rng[:-m]
        # 未確定部分のまま
        dp[:,m] += prev[:,m] * m
        # 未確定部分を広げる
        dp[:N-m,m+1] += prev[:N-m,m] * (N-m-rng[:N-m])
    dp %= MOD

answer = dp[N,0]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9+7

N,M = map(int,read().split())

"""
・既に強連結成分として確定している町の個数
・訪問済だけれど強連結成分には入っていない町の個数
に対する場合の数を持ってdp
"""

dp = np.zeros((N+1,N+1),np.int64)
dp[1,0] = 1

rng = np.arange(N+1,dtype=np.int64)

for _ in range(M):
    prev = dp
    dp = np.zeros_like(prev)
    # 強連結成分から出発する場合。
    dp[:,0] += prev[:,0] * rng
    dp[:,1] += prev[:,0] * rng[::-1]
    # 未確定部分から
    for m in range(1,N):
        # 強連結成分に戻る
        dp[m:,0] += prev[:-m,m] * rng[:-m]
        # 未確定部分のまま
        dp[:,m] += prev[:,m] * m
        # 未確定部分を広げる
        dp[:,m+1] += prev[:,m] * (N-m-rng)
    dp %= MOD

answer = dp[N,0]
print(answer)

Submission status: Memory Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    dp = [[[0] * N for _ in range(N+1)] for _ in range(M+1)]
    dp[0][1][0] = 1
    for i in range(M):
        for j in range(N+1):
            for k in range(N):
                dp[i+1][j][k] = (dp[i+1][j][k] + dp[i][j][k] * k)%mod
                if k+1 < N:
                    dp[i+1][j][k+1] = (dp[i+1][j][k+1] + dp[i][j][k] * (N - j - k))%mod
                if j+k <= N:
                    dp[i+1][j+k][0] = (dp[i+1][j+k][0] + dp[i][j][k] * j)%mod
    print(dp[-1][N][0])


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

Solution code:
mod=10**9+7

N,M=map(int,input().split())
dp=[[[0 for i in range(N+1)] for j in range(N+1)] for k in range(M+1)]

dp[M][N][N]=1

for i in range(M-1,-1,-1):
    for k in range(1,N+1):
        for j in range(k,N+1):
            if j==k:
                if j<N:
                    dp[i][j][k]=(j*dp[i+1][j][k]+(N-j)*dp[i+1][j+1][k])%mod
                else:
                    dp[i][j][k]=(N*dp[i+1][j][k])%mod
            else:
                if j<N:
                    dp[i][j][k]=(k*dp[i+1][j][j]+(N-j)*dp[i+1][j+1][k]+(j-k)*dp[i+1][j][k])%mod
                else:
                    dp[i][j][k]=(k*dp[i+1][j][j]+(N-k)*dp[i+1][j][k])%mod

print(dp[0][1][1])

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    dp = [[0] * N for _ in range(N+1)]
    dp[1][0] = 1
    for i in range(M):
        dp_new = [[0] * N for _ in range(N+1)]
        for j in range(N+1):
            for k in range(N):
                dp_new[j][k] = (dp_new[j][k] + dp[j][k] * k)%mod
                if k+1 < N:
                    dp_new[j][k+1] = (dp_new[j][k+1] + dp[j][k] * (N - j - k))%mod
                if j+k <= N:
                    dp_new[j+k][0] = (dp_new[j+k][0] + dp[j][k] * j)%mod
        dp = dp_new
    print(dp[N][0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod=10**9+7

N,M=map(int,input().split())
dp=[[0 for i in range(N+1)] for j in range(N+1)]
dp[N][N]=1

for i in range(M-1,-1,-1):
    for k in range(1,N+1):
        for j in range(k,N+1):
            if j==k:
                if j<N:
                    dp[j][k]=(j*dp[j][k]+(N-j)*dp[j+1][k])%mod
                else:
                    dp[j][k]=(N*dp[j][k])%mod
            else:
                if j<N:
                    dp[j][k]=(k*dp[j][j]+(N-j)*dp[j+1][k]+(j-k)*dp[j][k])%mod
                else:
                    dp[j][k]=(k*dp[j][j]+(N-k)*dp[j][k])%mod

print(dp[1][1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
mod = 10**9+7
dp = [[[0 for i in range(j+1)] for j in range(n+1)] for k in range(m+1)]
dp[0][1][1] = 1
for i in range(m):
  for j in range(n+1):
    for k in range(j+1):
      x = dp[i][j][k]
      if j < n:
        dp[i+1][j+1][k] += x*(n-j)
        dp[i+1][j+1][k] %= mod
      dp[i+1][j][j] = (dp[i+1][j][j]+x*k)%mod
      dp[i+1][j][k] = (dp[i+1][j][k]+x*(j-k))%mod
print(dp[m][n][n])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
MOD = 10**9+7
dpscc = [[0]*(N+1) for _ in range(N+1)]
dpus = [[0]*(N+1) for _ in range(N+1)]
dpscc[1][0] = 1

for m in range(M):
    dpscc2 = [[0]*(N+1) for _ in range(N+1)]
    dpus2 = [[0]*(N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(N+1-i):
            kscc = dpscc[i][j]
            kus = dpus[i][j]
            dpscc2[i][j] = (dpscc2[i][j] + i*kscc) % MOD
            dpus2[i][j] = (dpus2[i][j] + j*(kus+kscc)) % MOD
            dpscc2[i+j][0] = (dpscc2[i+j][0] + i*kus) % MOD
            if N-i-j:
                dpus2[i][j+1] = (dpus2[i][j+1] + (N-i-j)*(kus+kscc)) % MOD
    
    dpscc = [d[:] for d in dpscc2]
    dpus = [d[:] for d in dpus2]
print(dpscc[N][0])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10**9+7

N,M = map(int,read().split())

"""
・合計の訪問済の町の個数
・訪問済だけれど強連結成分には入っていない町の個数
に対する場合の数を持ってdp
"""

dp = np.zeros((N+1,N+1),np.int64)
dp[1,0] = 1
for _ in range(M):
    prev = dp
    dp = np.zeros_like(prev)
    # 強連結成分にもどる
    dp[:,0] += (prev[:,:] * (np.arange(N+1)[:,None] - np.arange(N+1)[None,:])).sum(axis=1)
    # 未確定部分内で
    dp[:,:] += prev[:,:] * np.arange(N+1)[None,:]
    # 未確定部分の拡張
    dp[1:,1:]+= prev[:-1,:-1] * np.arange(N,0,-1)[:,None]
    dp %= MOD

answer = dp[N,0]
print(answer)

Submission status: Accepted

Solution code:
input = raw_input
range = xrange
n, m = map(int,input().split())
MOD = 10**9+7

dp = [[0]*(n) for i in range(n+1)]
dp[1][0] = 1
for i in range(m):
    new = [[0]*(n) for i in range(n+1)]
    for j in range(1, n+1):
        for k in range(n-j+1):
            pv = dp[j][k]
            if k != n-j: new[j][k+1] = (new[j][k+1] + pv * (n-j-k)) % MOD
            new[j][k] = (new[j][k] + pv * k) % MOD
            new[j+k][0] = (new[j+k][0] + pv * j) % MOD
    dp = new
print(dp[n][0])