Submission #7885080

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
const ll mod=1e9+7;
ll mu(ll a,ll b){
  return (ll)a*b%mod;
}
ll ad(ll a,ll b){
  if((a+=b)>=mod)a-=mod;
  return a;
}
ll pw(ll a,ll b,ll c=1LL){
  for(;b;b>>=1,a=mu(a,a))if(b&1)c=mu(c,a);
  return c;
}
ll dv(ll a,ll b){
  return mu(a,pw(b,mod-2));
}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n,m;

  cin >> n >> m;
  vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(n+1, vector<int>(n+1)));
  //  int dp[m+1][n+1][n+1];//日にち、最初の町含む連結成分、孤立点
  //  cout << "" << endl;
  rep(i,m+1) rep(j,n+1) rep(l,n+1){
    dp[i][j][l]=0;
  }
  dp[0][1][n-1]=1;
  rep(i,m){
    rep(j,n+1){
      rep(l,n+1){
	if(j+l>n)continue;
	dp[i+1][j][l] =ad(mu(dp[i][j][l],(n-j-l)),dp[i+1][j][l]);
	if(l>=1) dp[i+1][j][l-1] = ad(mu(dp[i][j][l],l), dp[i+1][j][l-1]);
	dp[i+1][n-l][l] =ad(mu(dp[i][j][l],j),dp[i+1][n-l][l]);
	//	cout << "day conect alone " << i << " " << j <<  " " << l << " " <<dp[i][j][l] << endl;
      }
    }
    //    cout << "day "<< i << endl;
  }
  cout << dp[m][n][0] << endl;
  

  
  //  cout << endl << endl;
  //  cout << static_cast<double>(clock()) / CLOCKS_PER_SEC << "s"<<endl;
  return 0;
    

}

Submission Info

Judge Result