Submission #7096008

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;
ll N, M;
ll Prev[605][605][2];
ll Next[605][605][2];

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    Prev[1][0][0] = 1;
    ll minus;
    while(M--) {
        if(M == 0) minus = Prev[N][0][0] * N % mod;
        for(int i = 0; i <= N; i++) {
            for(int j = 0; j <= N; j++) {
                for(int k = 0; k <= 1; k++) {
                    Next[i][j][k] = 0;
                }
            }
        }
        for(ll i = 0; i <= N; i++) {
            for(ll j = 0; j <= N; j++) {
                Next[i][j][0] += Prev[i][j][0] * i;
                Next[i][j][1] += Prev[i][j][0] * j;
                Next[i][j+1][1] += Prev[i][j][0] * (N - i - j);
                Next[i+j][0][0] += Prev[i][j][1] * i;
                Next[i][j][1] += Prev[i][j][1] * j;
                Next[i][j+1][1] += Prev[i][j][1] * (N - i - j);
                Next[i][j][0] %= mod;
                Next[i][j][1] %= mod;
                Next[i][j+1][1] %= mod;
                Next[i+j][0][0] %= mod;
                Next[i][j+1][1] %= mod;
            }
        }
        swap(Next, Prev);
        /*
        cerr << endl;
        cerr << M << endl;
        for(int i = 0; i <= N; i++) {
            for(int j = 0; j <= N; j++) {
                cerr << i << " " << j << " " << Prev[i][j][0] << " " << Prev[i][j][1] << endl;
            }
        }
        */
    }
    cerr << minus << endl;
    cerr << Prev[N][0][1] << endl;
    cout << (Prev[N][0][0] - minus + mod) % mod << endl;
    return 0;
}

Submission Info

Judge Result