Submission #6220930
Source Code Expand
#include <bits/stdc++.h> #define err(args...) {} #ifdef DEBUG #include "_debug.cpp" #endif using namespace std; using ll = long long; using ld = long double; template <typename T> using lim = numeric_limits<T>; template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; } template <typename T> constexpr T fpow(T x, ll y, T identity = 1) { return fpow_eq(x, y, identity); } template <typename T> constexpr T fpow_eq(T& x, ll y, T identity = 1) { for(; y > 0; x *= x, y >>= 1) { if(y & 1) { identity *= x; } } return x = identity; } #ifdef __TOTIENT_INCLUDED_ template <int M, int PHI_M = phi(M)> struct modint { #else template <int M, int PHI_M> struct modint { #endif static constexpr int MOD = M; int val; constexpr modint() : val(0) {} constexpr modint(int val) : val(val % M) { val += val < 0 ? M : 0; } constexpr modint(long long val) : modint(int(val % M)) {} constexpr modint(const modint& m) : val(m.val) {} constexpr explicit operator int() const { return val; } constexpr bool operator==(const modint& y) const { return val == y.val; } constexpr bool operator!=(const modint& y) const { return val != y.val; } constexpr bool operator< (const modint& y) const { return val < y.val; } constexpr bool operator<=(const modint& y) const { return val <= y.val; } constexpr bool operator> (const modint& y) const { return val > y.val; } constexpr bool operator>=(const modint& y) const { return val >= y.val; } constexpr modint& operator=(const modint& y) { val = y.val; return *this; } constexpr modint& operator+=(const modint& y) { val += y.val; val -= val >= M ? M : 0; return *this; } constexpr modint& operator-=(const modint& y) { val -= y.val; val += val < 0 ? M : 0; return *this; } constexpr modint& operator*=(const modint& y) { val = ll(val) * y.val % M; return *this; } constexpr modint& operator/=(const modint& y) { val = ll(val) * fpow(y, PHI_M - 1).val % M; return *this; } constexpr modint& operator^=(ll y) { fpow_eq(*this, y); return *this; } constexpr modint operator+(const modint& y) const { return modint(val) += y; } constexpr modint operator-(const modint& y) const { return modint(val) -= y; } constexpr modint operator*(const modint& y) const { return modint(val) *= y; } constexpr modint operator/(const modint& y) const { return modint(val) /= y; } constexpr modint operator^(ll y) const { return modint(val) ^= y; } constexpr modint operator-() const { return modint(0) -= *this; } constexpr modint operator~() const { return modint(1) /= *this; } constexpr modint& operator++() { val = val == M - 1 ? 0 : val + 1; return *this; } constexpr modint& operator--() { val = val == 0 ? M - 1 : val - 1; return *this; } constexpr modint operator++(int) { modint m = *this; ++(*this); return m; } constexpr modint operator--(int) { modint m = *this; --(*this); return m; } friend constexpr modint operator+(long long x, const modint& y) { return modint(x) + y; } friend constexpr modint operator*(long long x, const modint& y) { return modint(x) * y; } friend constexpr modint operator-(long long x, const modint& y) { return modint(x) - y; } friend constexpr modint operator/(long long x, const modint& y) { return modint(x) / y; } friend ostream& operator<<(ostream& os, const modint& m) { return os << m.val; } friend istream& operator>>(istream& is, modint& m) { ll val; is >> val; m = modint(val); return is; } }; constexpr int M = 1'000'000'007; using mint = modint<M, M - 1>; mint operator""_m(unsigned long long int x) { return mint(ll(x)); } template <typename T = mint> T fact(int n) { static vector<T> fac = {1}; while(fac.size() <= n) { fac.push_back(fac.back() * int(fac.size())); } return fac[n]; } template <typename T = mint> T fact_inv(int n) { static vector<T> inv_fac = {1}; while(inv_fac.size() <= n) { inv_fac.push_back(inv_fac.back() / int(inv_fac.size())); } return inv_fac[n]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; const int N = 300; static mint C[N+1][N+1][N+1]; C[0][n][n] = 1; for(int n_moves = 1; n_moves <= m; n_moves++) { for(int n_visited = 1; n_visited <= n; n_visited++) { for(int n_in_scc = 1; n_in_scc <= n_visited; n_in_scc++) { C[n_moves][n_visited][n_in_scc] = C[n_moves - 1][n_visited][n_in_scc] * (n_visited - n_in_scc) + C[n_moves - 1][n_visited][n_visited] * n_in_scc + (n_visited < n ? C[n_moves - 1][n_visited + 1][n_in_scc] : 0); } } } cout << C[m][1][1] * fact(n - 1) << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | verngutz |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 4954 Byte |
Status | AC |
Exec Time | 196 ms |
Memory | 106496 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 | 1 ms | 256 KB |
01-02.txt | AC | 1 ms | 256 KB |
01-03.txt | AC | 21 ms | 104704 KB |
01-04.txt | AC | 2 ms | 640 KB |
01-05.txt | AC | 21 ms | 104832 KB |
01-06.txt | AC | 37 ms | 105216 KB |
01-07.txt | AC | 184 ms | 106368 KB |
01-08.txt | AC | 194 ms | 106496 KB |
01-09.txt | AC | 195 ms | 106496 KB |
01-10.txt | AC | 196 ms | 106496 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 66 ms | 105600 KB |
sample-03.txt | AC | 99 ms | 55168 KB |