Submission #993920

---

Source Code Expand

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long LL;

LL powmod(LL a, LL n){
	if(n == 0) return 1;
	if(n % 2) return (a*powmod(a,n-1)) % MOD;
	LL c = powmod(a,n/2);
	return (c*c) % MOD;
}
LL inv(LL a){
	return powmod(a,MOD-2) % MOD;
}


int main(){
	LL n, m;
	cin >> n >> m;

	/*LL dp[310][310]; // how many left to visit;
	for(LL i = 0; i <= n; i++) dp[0][i] = 0;
	dp[0][n] = 1;
	for(LL j = 0; j < m; j++){
		for(LL i = 0; i <= n; i++) dp[j+1][i] = 0;
		for(LL i = 0; i <= n; i++){
			dp[j+1][i] += (n-i) * dp[j][i];
			dp[j+1][i] %= MOD;
			if(i > 0){
				dp[j+1][i-1] += (i) * dp[j][i];
				dp[j+1][i-1] %= MOD;
			}
		}
	}*/
	LL dp[2][310][310]; // home, unvis;
	for(LL i = 0; i < 310; i++) for(int j = 0; j < 310; j++) dp[0][i][j] = dp[1][i][j] = 0;
	dp[0][1][n-1] = 1;
	for(LL c = 0; c < m; c++){
		for(LL i = 0; i < 310; i++) for(int j = 0; j < 310; j++) dp[1-c%2][i][j] = 0;
		for(LL j = 0; j <= n; j++){
			for(LL k = 0; k + j <= n; k++){
				dp[1-c%2][n-k][k] += j*dp[c%2][j][k];
				dp[1-c%2][n-k][k] %= MOD;

				if(k > 0) dp[1-c%2][j][k-1] += k*dp[c%2][j][k];
				if(k > 0) dp[1-c%2][j][k-1] %= MOD;

				if(n-j-k > 0) dp[1-c%2][j][k] += (n-j-k)*dp[c%2][j][k];
				if(n-j-k > 0) dp[1-c%2][j][k] %= MOD;

			}
		}
	}
	cout << dp[m%2][n][0] << endl;
}

Submission Info

Judge Result