Submission #1007696

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
#define mod 1000000007

#define MAX_N 305
#define MAX_M 305

int N, M;

void input()
{
  cin >> N >> M;
}

//パスの長さ パスに含まれる頂点の数 強連結の数
LL dp[MAX_N][MAX_N][MAX_N];
LL solve()
{
  memset(dp, 0, sizeof(dp));
  dp[0][1][1] = 1;

  for (int i = 0; i < M; i++) {
    for (int j = 0; j <= N; j++) {
      for (int k = 0; k <= N; k++) {

        dp[i+1][j+1][k] += dp[i][j][k] * (N-j);
        dp[i+1][j+1][k] %= mod;

        if(j >= k){
          dp[i+1][j][k] += dp[i][j][k] * (j-k);
          dp[i+1][j][k] %= mod;
        }

        dp[i+1][j][j] += dp[i][j][k]*k;
        dp[i+1][j][j] %= mod;

      }
    }
  }

  return dp[M][N][N];
}

int main()
{
  input();

  cout << solve() << endl;

  return 0;
}

Submission Info

Judge Result