Submission #992886

---

Source Code Expand

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <random>
#include <vector>
#include <array>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n==0) ? 1 : 10*TEN(n-1); }
int bsr(int x) { return 31 - __builtin_clz(x); }


template<class T>
T pow(T x, ll n, T r = 1) {
    while (n) {
        if (n & 1) r *= x;
        x *= x;
        n >>= 1;
    }
    return r;
}

template<uint MD>
struct ModInt {
    uint v;
    ModInt() : v{0} {}
    ModInt(ll v) : v{normS(v%MD+MD)} {}
    static uint normS(const uint &x) {return (x<MD)?x:x-MD;};
    static ModInt make(const uint &x) {ModInt m; m.v = x; return m;}
    ModInt operator+(const ModInt &r) const {return make(normS(v+r.v));}
    ModInt operator-(const ModInt &r) const {return make(normS(v+MD-r.v));}
    ModInt operator*(const ModInt &r) const {return make((ull)v*r.v%MD);}
    ModInt& operator+=(const ModInt &r) {return *this=*this+r;}
    ModInt& operator-=(const ModInt &r) {return *this=*this-r;}
    ModInt& operator*=(const ModInt &r) {return *this=*this*r;}
    static ModInt inv(const ModInt &x) {
        return pow(ModInt(x), MD-2);
    }
};
using Mint = ModInt<TEN(9)+7>;

const int MN = 330;
int n;


Mint dp[MN][MN][MN];
bool used[MN][MN][MN] = {};
Mint calc(int m, int a, int b) {
    if (m == 0) {
        if (a == n) return 1;
        return 0;
    }
    if (used[m][a][b]) return dp[m][a][b];
    used[m][a][b] = true;
    Mint &ans = dp[m][a][b]; ans = 0;
    ans += calc(m-1, a+b, 0) * a;
    ans += calc(m-1, a, b) * b;
    ans += calc(m-1, a, b+1) * (n-a-b);
    return ans;
}

int main() {
    cout << setprecision(20);
    int m;
    cin >> n >> m;
    cout << calc(m, 1, 0).v << endl;
    return 0;
}

Submission Info

Judge Result