Submission #995322

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <sstream>

#include <vector>
#include <set>
#include <bitset>
#include <map>
#include <deque>
#include <string>

#include <algorithm>
#include <numeric>

#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>

#define pb push_back
#define pbk pop_back
#define mp make_pair
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define len(a) ((int) (a).size())

#ifdef CUTEBMAING
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif

using namespace std;

typedef long long int64;
typedef long double ld;
typedef unsigned long long lint;

const int inf = (1 << 30) - 1;
const int64 linf = (1ll << 62) - 1;
const int N = 400;
const int M = 1e9 + 7;

inline int power(int a, int b) {
    int res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = (1ll * res * a) % M;
        }
        a = (1ll * a * a) % M;
    }
    return res;
}

int n, m;
int wdp[N][N];
int dp[N][N];
int pw[N][N];

int fact[N], ifact[N];

inline int cnk(int n, int k) {
    return (((1ll * fact[n] * ifact[k]) % M) * ifact[n - k]) % M;
}

int main() {
#ifdef XCODE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cin >> n >> m;
    fact[0] = 1;
    ifact[0] = 1;
    for (int i = 1; i <= m; i++) {
        fact[i] = (1ll * fact[i - 1] * i) % M;
        ifact[i] = power(fact[i], M - 2);
    }
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= m; j++) {
            pw[j][i] = i == 0 ? 1 : (1ll * pw[j][i - 1] * j) % M;
        }
    }
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= i; j++) {
            wdp[i][j] = pw[j][i];
            for (int z = 1; z < j; z++) {
                wdp[i][j] = (wdp[i][j] - 1ll * cnk(j, z) * wdp[i][j - z]) % M;
                if (wdp[i][j] < 0) {
                    wdp[i][j] += M;
                }
            }
        }
    }
    dp[0][1] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 1; j <= n; j++) {
            if (!dp[i][j]) {
                continue;
            }
            for (int l = 0; j + l <= n; l++) {
                int cur2 = cnk(n - j, l);
                for (int z = l; z <= m - i - 1; z++) {
                    int cur = (((1ll * j * wdp[z][l]) % M) * cur2) % M;
                    dp[i + z + 1][j + l] = (dp[i + z + 1][j + l] + 1ll * cur * dp[i][j]) % M;
                }
            }
        }
    }
    cout << dp[m][n] << endl;
    return 0;
}

Submission Info

Judge Result