結果
問題 | No.140 みんなで旅行 |
ユーザー | noya2 |
提出日時 | 2022-04-07 23:30:54 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 19,501 bytes |
コンパイル時間 | 4,898 ms |
コンパイル使用メモリ | 282,048 KB |
実行使用メモリ | 817,408 KB |
最終ジャッジ日時 | 2024-05-06 00:48:21 |
合計ジャッジ時間 | 7,357 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 61 ms
19,584 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | MLE | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
ソースコード
#include <bits/stdc++.h> /* #include <boost/multiprecision/cpp_dec_float.hpp> #include <boost/multiprecision/cpp_int.hpp> namespace mp = boost::multiprecision; using bint = mp::cpp_int; */ #include <atcoder/all> #define rep(i,n) for (int i = 0; i < int(n); ++i) #define repp(i,n,m) for (int i = m; i < int(n); ++i) #define repb(i,n) for (int i = int(n)-1; i >= 0; --i) #define fi first #define se second #define endl "\n" using namespace std; using namespace atcoder; using ll = long long; using ld = long double; using P = pair<int, int>; using PL = pair<long long, long long>; using Pxy = pair<long double, long double>; using pil = pair<int,ll>; using pli = pair<ll,int>; using ppi = pair<P,int>; using pip = pair<int,P>; const int INF = 1001001007; const long long mod1 = 1000000007LL; const long long mod2 = 998244353LL; const ll inf = 2e18; const ld pi = 3.14159265358979323; const ld eps = 1e-7; const char _ = ' '; template<class T>istream &operator>>(istream &is,vector<T> &v){for(auto &e:v)is>>e;return is;} template<class T>ostream &operator<<(ostream &os,const vector<T> &v){if(v.size()!=0){rep(i,v.size())os<<v[i]<<(i+1==v.size()?"":" ");}return os;} template<class T>istream &operator>>(istream &is,vector<vector<T>> &v){for(auto &e:v)is>>e;return is;} template<class T>ostream &operator<<(ostream &os,const vector<vector<T>> &v){if(v.size()!=0){for(auto &e:v)os<<e;}return os;} template<typename T>bool range(T a,T b,T x){return (a<=x&&x<b);} template<typename T>bool rrange(T a,T b,T c,T d,T x,T y){return (range(a,c,x)&&range(b,d,y));} template<typename T>void rev(vector<T> &v){reverse(v.begin(),v.end());} void revs(string &s) {reverse(s.begin(),s.end());} template<typename T>void sor(vector<T> &v, int f=0){sort(v.begin(),v.end());if(f!=0) rev(v);} template<typename T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} template<typename T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<typename T>void eru(vector<T> &v){sor(v);v.erase(unique(v.begin(),v.end()),v.end());} template<typename T>T cel(T a,T b){if(a%b==0)return a/b;return a/b +1;} void o(){cout<<"!?"<<endl;} template<typename T>void o(T a){cout<<a<<endl;} template<typename T,typename U>void o2(T a,U b){cout<<a<<_<<b<<endl;} template<typename T,typename U>void o2(pair<T,U> a){o2(a.first,a.second);} template<typename T,typename U,typename V>void o3(T a,U b,V c){cout<<a<<_<<b<<_<<c<<endl;} template<typename T>void mout(T a){cout<<a.val()<<endl;} void yes(){cout << "Yes" << endl;} void no (){cout << "No" << endl;} void yn (bool t){if(t)yes();else no();} template<typename T>void dame(bool t, T s){if(!t){cout << s << endl;exit(0);}} void fast_io(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);} vector<int> dx = {0,1,0,-1}; vector<int> dy = {1,0,-1,0}; const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string alp = "abcdefghijklmnopqrstuvwxyz"; const string NUM = "0123456789"; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll mpow(ll x,ll n,ll m){if(n==0)return 1LL;x%=m;ll a=mpow(x,n/2,m);a=a*a%m;return (n&1)?a*x%m:a;} template<typename T> ll tentou(vector<T> ar){ int n = ar.size(); set<T> st; rep(i,n) st.insert(ar[i]); map<T,int> mp; int ind = 0; for (T x : st){ mp[x] = ind; ind++; } fenwick_tree<ll> fw(ind); ll ans = 0; rep(i,n){ int a = mp[ar[i]]; ans += i - fw.sum(0,a+1); fw.add(a,1); } return ans; } struct edge{ int from, to, idx; long long cost; edge(int _from = -1, int _to = -1, long long _cost = 1LL, int _idx = -1) : from(_from), to(_to), cost(_cost), idx(_idx) {} }; struct vertex{ vector<edge> adj; }; struct Graph{ int n; vector<vertex> vs; void add_edge(int from, int to, long long cost = 1LL){ assert(0 <= from && from < n); assert(0 <= to && to < n); vs[from].adj.emplace_back(edge(from,to,cost)); } void add_dual_edge(int from, int to, long long cost = 1LL){ assert(0 <= from && from < n); assert(0 <= to && to < n); vs[from].adj.emplace_back(edge(from,to,cost)); vs[to].adj.emplace_back(edge(to,from,cost)); } Graph(int _n) : n(_n) , vs(n) {} vector<long long> dijkstra(int s){ using pli = pair<long long, int>; priority_queue<pli, vector<pli>, greater<pli>> pque; vector<long long> dist(n,inf); dist[s] = 0LL; pque.push(pli(0,s)); while (!pque.empty()){ pli p = pque.top(); pque.pop(); if (dist[p.second] < p.first) continue; for (edge x : vs[p.second].adj){ if (dist[x.to] > p.first + x.cost){ dist[x.to] = p.first + x.cost; pque.push(pli(dist[x.to],x.to)); } } } return dist; } vector<long long> bfs01(int s){ deque<int> que; vector<long long> dist(n,inf); dist[s] = 0LL; que.push_front(s); while (!que.empty()){ int p = que.front(); que.pop_front(); for (edge x : vs[p].adj){ if (dist[x.to] > dist[p] + x.cost){ dist[x.to] = dist[p] + x.cost; if (x.cost == 0LL) que.push_front(x.to); else que.push_back(x.to); } } } return dist; } vector<int> dfs(int s){ vector<int> ans; vector<int> vis(n,0); _dfs(s,ans,vis); return ans; } private: void _dfs(int s, vector<int> &ans, vector<int> &vis){ vis[s]++; for (edge x : vs[s].adj){ if (vis[x.to] == 0){ _dfs(x.to,ans,vis); } } ans.emplace_back(s); } }; struct Tree{ Tree(int _n, int _root = 0) : n(_n), root(_root) { assert(0 <= root && root < n); initialize(); } void add_edge(int from, int to, long long cost = 1LL, int _idx = -1){ assert(0 <= from && from < n); assert(0 <= to && to < n); if (_idx == -1) _idx = m, m++; assert(0 <= _idx && _idx < n-1); assert(edge_idx_cnt[_idx] == 0); edge_idx_cnt[_idx]++; vs[from].adj.emplace_back(edge(from,to,cost,_idx)); es[_idx] = edge(from,to,cost,_idx); } void add_dual_edge(int from, int to, long long cost = 1LL, int _idx = -1){ assert(0 <= from && from < n); assert(0 <= to && to < n); if (_idx == -1) _idx = m, m++; assert(0 <= _idx && _idx < n-1); assert(edge_idx_cnt[_idx] == 0); edge_idx_cnt[_idx]++; vs[from].adj.emplace_back(edge(from,to,cost,_idx)); vs[to].adj.emplace_back(edge(to,from,cost,_idx)); es[_idx] = edge(from,to,cost,_idx); } int size(){return n;} int parent(int v){ assert(0 <= v && v < n); if (is_done_par_rdist_init == false) par_rdist_init(); return par[v]; } int depth(int v){ assert(0 <= v && v < n); if (dep[v] != -1) return dep[v]; if (v == root) return dep[v] = 0; return dep[v] = depth(parent(v)) + 1; } int subtree_size(int v){ assert(0 <= v && v < n); if (sub[v] != 0) return sub[v]; sub[v] = 1; for (edge x : vs[v].adj){ if (x.to != parent(v)) sub[v] += subtree_size(x.to); } return sub[v]; } int lca(int u, int v){ assert(0 <= u && u < n); assert(0 <= v && v < n); if (is_done_lca_init == false) lca_init(); if (depth(u) > depth(v)) swap(u,v); for (int i = 0; i < 30; i++) if ((depth(v) - depth(u)) >> i & 1) v = par2[i][v]; if (u == v) return u; for (int k = 29; k >= 0; k--){ if (par2[k][u] != par2[k][v]) { u = par2[k][u]; v = par2[k][v]; } } return par2[0][u]; } long long dist(int u, int v){ assert(0 <= u && u < n); assert(0 <= v && v < n); if (is_done_par_rdist_init == false) par_rdist_init(); return rdist[u] + rdist[v] - rdist[lca(u,v)] * 2LL; } vector<int> path(int f, int t){ assert(0 <= f && f < n); assert(0 <= t && t < n); int v = lca(f,t); vector<int> fp = {f}; vector<int> tp = {t}; int fn = f, tn = t; while (fn != v){ fn = parent(fn); fp.emplace_back(fn); } while (tn != v){ tn = parent(tn); tp.emplace_back(tn); } for (int i = int(tp.size()) - 2; i >= 0; i--){ fp.emplace_back(tp[i]); } return fp; } vector<long long> alldists(int v){ assert(0 <= v && v < n); if (v == 0) return rdist; vector<long long> dists(n,1e18); vector<int> vis(n,0); dists[v] = 0LL; queue<int> que; que.push(v); while (!que.empty()){ int p = que.front(); que.pop(); vis[p]++; for (edge x : vs[p].adj){ if (vis[x.to] == 0){ dists[x.to] = dists[p] + x.cost; que.push(x.to); } } } return dists; } vector<int> dfs(int v){ assert(0 <= v && v < n); vector<int> ans; vector<int> vis(n,0); _dfs(v,vis,ans); return ans; } edge to_parent(int v){ assert(0 <= v && v < n && v != root); if (is_done_par_rdist_init == false) par_rdist_init(); return es[epar[v]]; } vector<vertex> vs; private: int n; int m; int root; int idx_vhfs; bool is_done_lca_init; bool is_done_par_rdist_init; vector<edge> es; vector<int> edge_idx_cnt; vector<int> par; vector<int> epar; vector<int> dep; vector<int> sub; vector<int> top; vector<long long> rdist; vector<vector<int>> par2; void initialize(){ m = 0; is_done_lca_init = false; is_done_par_rdist_init = false; vs.resize(n); es.resize(n-1); edge_idx_cnt.resize(n-1,0); dep.resize(n,-1); sub.resize(n,0); } void lca_init(){ par2.resize(30,vector<int>(n,-1)); for (int i = 0; i < n; i++) par2[0][i] = parent(i); for (int i = 0; i < 29 ; i++) { for (int j = 0; j < n; j++) { if (par2[i][j] < 0) par2[i+1][j] = -1; else par2[i+1][j] = par2[i][par2[i][j]]; } } is_done_lca_init = true; } void par_rdist_init(){ par.resize(n,-2); epar.resize(n); rdist.resize(n,-1); par[root] = -1; rdist[root] = 0; queue<int> que; que.push(root); while (!que.empty()){ int p = que.front(); que.pop(); for (edge x : vs[p].adj){ if (par[x.to] == -2){ par[x.to] = p; epar[x.to] = x.idx; rdist[x.to] = rdist[p] + x.cost; que.push(x.to); } } } is_done_par_rdist_init = true; } void _dfs(int v, vector<int> &vis, vector<int> &ans){ vis[v]++; for (edge x : vs[v].adj){ if (vis[x.to] == 0) _dfs(x.to,vis,ans); } ans.emplace_back(v); } }; template<typename T> struct doubling{ vector<T> vec; doubling (vector<T> _vec) : vec(_vec) {} map<T,ll> mp; ll length_of_loop = -1; ll top_of_loop = -1; void init(){ ll ind = 0; for (T x : vec){ if (mp.find(x) == mp.end()) mp[x] = ind, ind++; else { length_of_loop = ind - mp[x]; top_of_loop = mp[x]; break; } } } ll len(){ if (length_of_loop == -1) init(); return length_of_loop; } ll top(){ if (top_of_loop == -1) init(); return top_of_loop; } T get(ll n){ assert(0 <= n); if (n < top()) return vec[n]; ll d = n - top(); return vec[top() + (d % len())]; } }; struct Mo{ vector<int> left, right, order, v; int width, nl, nr, ptr; Mo (int n = 0) : width(sqrt(n)), nl(0), nr(0), ptr(0), left(0), right(0), v(n,-1) {} void insert(int l, int r){ // [l,r) left.emplace_back(l); right.emplace_back(r); } void build(){ // sort all query order.resize(left.size()); iota(order.begin(),order.end(),0); sort(order.begin(),order.end(),[&](int a, int b){ if(left[a] / width != left[b] / width) return left[a] < left[b]; return right[a] < right[b]; }); } int process(){ // do 1 query if (ptr == int(order.size())) return -1; const int id = order[ptr]; while (nl > left[id]) distribute(--nl); while (nl < left[id]) distribute(nl++); while (nr > right[id]) distribute(--nr); while (nr < right[id]) distribute(nr++); return order[ptr++]; } inline void distribute(int idx){ // x x x (nl) o o o (nr) x x ... v[idx] *= -1; if (v[idx] == 1) add(idx); else del(idx); } void add(int idx); void del(int idx); }; template<typename T> struct Matrix{ int rows; int cols; vector<vector<T>> m; Matrix (int h = 0, int w = 0, T init = T(0)) : m(h,vector<T>(w,init)), rows(h), cols(w){} Matrix (vector<vector<T>> _init) : m(_init), rows(_init.size()), cols(_init.at(0).size()){} vector<T> operator[](const int i) const {return m[i];} vector<T>& operator[](const int i) {return m[i];} Matrix &operator+= (const Matrix &r){ assert(this->rows == r.rows && this->cols == r.cols); for (int i = 0; i < r.rows; ++i){ for (int j = 0; j < r.cols; ++j){ m[i][j] += r.m[i][j]; } } return *this; } Matrix &operator-= (const Matrix &r){ assert(this->rows == r.rows && this->cols == r.cols); for (int i = 0; i < r.rows; ++i){ for (int j = 0; j < r.cols; ++j){ m[i][j] -= r.m[i][j]; } } return *this; } Matrix &operator*= (const Matrix &r){ assert(this->cols == r.rows); Matrix res(rows, r.cols); for (int i = 0; i < rows; ++i){ for (int j = 0; j < r.cols; ++j){ for (int k = 0; k < r.rows; ++k){ res[i][j] += m[i][k] * r.m[k][j]; } } } return *this = res; } Matrix operator+ (const Matrix &r) const {return Matrix(*this) += r;} Matrix operator- (const Matrix &r) const {return Matrix(*this) -= r;} Matrix operator* (const Matrix &r) const {return Matrix(*this) *= r;} bool operator== (const Matrix &r){ if (rows != r.rows || cols != r.cols) return false; for (int i = 0; i < r.rows; ++i){ for (int j = 0; j < r.cols; ++j){ if (m[i][j] != r.m[i][j]) return false; } } return true; } Matrix& operator+=(const T &r){ for (int i = 0; i < rows; ++i){ for (int j = 0; j < cols; ++j){ m[i][j] += r; } } return *this; } Matrix& operator-=(const T &r){ for (int i = 0; i < rows; ++i){ for (int j = 0; j < cols; ++j){ m[i][j] -= r; } } return *this; } Matrix& operator*=(const T &r){ for (int i = 0; i < rows; ++i){ for (int j = 0; j < cols; ++j){ m[i][j] *= r; } } return *this; } Matrix& operator/=(const T &r){ for (int i = 0; i < rows; ++i){ for (int j = 0; j < cols; ++j){ m[i][j] /= r; } } return *this; } Matrix operator+ (const T &r) const {return Matrix(*this) += r;} Matrix operator- (const T &r) const {return Matrix(*this) -= r;} Matrix operator* (const T &r) const {return Matrix(*this) *= r;} Matrix operator/ (const T &r) const {return Matrix(*this) /= r;} Matrix e(){ assert(this->rows == this->cols); Matrix res(this->rows, this->rows); for (int i = 0; i < rows; ++i) res[i][i] = 1; return res; } Matrix matpow(ll n){ assert(this->rows == this->cols); if (n == 0) return e(); Matrix f = matpow(n / 2); Matrix ans = f * f; if (n % 2 == 1) ans *= *this; return ans; } // for T = int, long long, double, long double void show(){ for (int i = 0; i < rows; ++i){ for (int j = 0; j < cols; ++j){ cout << m[i][j] << (j+1 == this->cols ? "\n" : " "); } } } }; template<class S, S op(S l, S r), S e()> struct Rui{ /* - op(e,x) = op(x,e) = x - op(l,opinv(l,lr)) = lr */ int n; vector<S> vec, lrui, rrui; Rui (vector<S> _vec) : n(int(_vec.size())), vec(_vec) { lrui.resize(n+1), rrui.resize(n+1); lrui[0] = rrui[n] = e(); for (int i = 0; i < n; i++) lrui[i+1] = op(lrui[i],vec[i]); for (int i = n; i > 0; i--) rrui[i-1] = op(rrui[i],vec[i-1]); } template<S opinv(S l, S lr)> S prod(int l, int r = -1){ // [l,r) if (r == -1) return vec[l]; return opinv(lrui[l],lrui[r]); } S nprod(int l, int r = -1){ // [0,l) * [r,n) if (r == -1) r = l+1; return op(lrui[l],rrui[r]); } }; struct MINT998244353{ using mint = modint998244353; vector<mint> kaijo, kainv; int N; MINT998244353 (int lim = 200000) : N(lim), kaijo(lim+1,1), kainv(lim+1,1) { rep(i,N) kaijo[i+1] = kaijo[i] * (i+1); rep(i,N) kainv[i+1] = kainv[i] / (i+1); } mint factrial(int x){return kaijo[x];} mint inv_factorial(int x){return kainv[x];} mint ncr(int n, int r){return kaijo[n] * kainv[r] * kainv[n-r];} template<typename T> vector<mint> beki(T r, int n = -1){ if (n == -1) n = N; vector<mint> res(n+1,1); rep(i,n) res[i+1] = res[i] * mint(r); return res; } vector<mint> vec_inv(vector<mint> &a){ vector<mint> res(a.size()); rep(i,int(a.size())) res[i] = a[i].inv(); return res; } }; int op(int a, int b){return a + b;} int e(){return 0;} int opinv(int a, int ab){return ab - a;} void solve(){ int n; cin >> n; using mint = modint1000000007; vector<vector<vector<mint>>> dp(n+1,vector<vector<mint>>(2*n+3,vector<mint>(n+1,0))); dp[0][0][0] = 1; rep(i,n) rep(j,2*n+1) rep(k,n){ if (j < k) continue; if (j == 0){ dp[i+1][j+1][k+1] += dp[i][j][k]; dp[i+1][j+2][k] += dp[i][j][k]; continue; } dp[i+1][j+1][k+1] += dp[i][j][k]; dp[i+1][j][k] += dp[i][j][k] * mint(k); dp[i+1][j][k+1] += dp[i][j][k] * mint(j - k); if (j > 0) dp[i+1][j][k] += dp[i][j][k] * mint(j) * mint(j-1); dp[i+1][j+1][k] += dp[i][j][k] * mint(j) * mint(2); dp[i+1][j+2][k] += dp[i][j][k]; } mint ans = 0; rep(i,n+1) { ans += dp[n][i][i]; //mout(ans); } mout(ans); } int main(){ fast_io(); int t = 1; //cin >> t; while (t--) solve(); }