Submission #1243594
Source Code Expand
#include <algorithm> #include <iostream> #include <cstdio> #include <map> #include <numeric> #include <cmath> #include <set> #include <sstream> #include <string> #include <vector> #include <queue> #include <stack> #include <complex> #include <string.h> #include <unordered_set> #include <unordered_map> #include <bitset> #include <iomanip> #include <sys/time.h> #include <tuple> #include <random> using namespace std; #define endl '\n' #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end()) typedef long long ll; typedef long double ld; typedef pair<int, int> P; typedef complex<double> comp; typedef vector< vector<ld> > matrix; struct pairhash { public: template<typename T, typename U> size_t operator()(const pair<T, U> &x) const { size_t seed = hash<T>()(x.first); return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2); } }; const int inf = 1e9 + 9; const ll mod = 1e9 + 7; const double eps = 1e-8; const double pi = acos(-1); ll N, M; ll dp[310][310][310]; ll mod_pow(ll x, ll n) { ll res = 1; while (n > 0) { if (n & 1) res = (res * x) % mod; x = (x * x) % mod; n >>= 1; } return res; } ll mod_inverse(ll x) { return mod_pow(x, mod-2); } const int max_n = 310; ll fact[max_n]; ll fact_inv[max_n]; void calc_fact() { fact[0] = 1; for (ll i = 1; i < max_n; i++) fact[i] = (fact[i-1] * i) % mod; fact_inv[max_n-1] = mod_inverse(fact[max_n-1]); for (ll i = max_n-2; i >= 0; i--) fact_inv[i] = (fact_inv[i+1] * (i+1)) % mod; } ll calc(ll n, ll k, ll m) { if (n == N && k ==0 && m == 0) return 1; if (!(n+k <= N && m >= 0)) return 0; if (dp[n][k][m] < 0) { dp[n][k][m] = (n * calc(n+k, 0, m-1) + calc(n, k+1, m-1)) % mod; dp[n][k][m] = (dp[n][k][m] + k * calc(n, k, m-1)) % mod; } return dp[n][k][m]; } ll solve() { calc_fact(); memset(dp, -1, sizeof(dp)); return calc(1, 0, M) * fact[N-1] % mod; } void input() { cin >> N >> M; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); input(); cout << solve() << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | assy |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2336 Byte |
Status | AC |
Exec Time | 197 ms |
Memory | 232960 KB |
Judge Result
Set Name | sample | all | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
all | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 58 ms | 232960 KB |
01-02.txt | AC | 58 ms | 232960 KB |
01-03.txt | AC | 58 ms | 232960 KB |
01-04.txt | AC | 58 ms | 232960 KB |
01-05.txt | AC | 58 ms | 232960 KB |
01-06.txt | AC | 85 ms | 232960 KB |
01-07.txt | AC | 195 ms | 232960 KB |
01-08.txt | AC | 197 ms | 232960 KB |
01-09.txt | AC | 197 ms | 232960 KB |
01-10.txt | AC | 197 ms | 232960 KB |
sample-01.txt | AC | 58 ms | 232960 KB |
sample-02.txt | AC | 126 ms | 232960 KB |
sample-03.txt | AC | 75 ms | 232960 KB |