結果
問題 | No.140 みんなで旅行 |
ユーザー | noya2 |
提出日時 | 2022-04-07 23:36:15 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 4,574 ms / 5,000 ms |
コード長 | 3,848 bytes |
コンパイル時間 | 5,223 ms |
コンパイル使用メモリ | 271,472 KB |
実行使用メモリ | 8,216 KB |
最終ジャッジ日時 | 2024-05-06 00:50:27 |
合計ジャッジ時間 | 27,939 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 44 ms
5,376 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 | AC | 4,547 ms
8,192 KB |
testcase_12 | AC | 25 ms
5,376 KB |
testcase_13 | AC | 6 ms
5,376 KB |
testcase_14 | AC | 4,574 ms
8,216 KB |
testcase_15 | AC | 4,477 ms
8,064 KB |
testcase_16 | AC | 1,034 ms
5,376 KB |
testcase_17 | AC | 325 ms
5,376 KB |
testcase_18 | AC | 3,028 ms
6,932 KB |
testcase_19 | AC | 3,549 ms
7,336 KB |
testcase_20 | AC | 224 ms
5,376 KB |
testcase_21 | AC | 3 ms
5,376 KB |
ソースコード
#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"; void solve(){ int n; cin >> n; using mint = modint1000000007; vector<vector<mint>> dp(2*n+3,vector<mint>(n+1,0)); dp[0][0] = 1; rep(i,n) { vector<vector<mint>> ep(2*n+3,vector<mint>(n+1,0)); rep(j,2*n+1) rep(k,n){ mint x = dp[j][k]; if (j < k) continue; if (j == 0){ ep[j+1][k+1] += x; ep[j+2][k] += x; continue; } ep[j+1][k+1] += x; ep[j][k] += x * mint(k); ep[j][k+1] += x * mint(j - k); ep[j][k] += x * mint(j) * mint(j-1); ep[j+1][k] += x * mint(j) * mint(2); ep[j+2][k] += x; } dp = ep; } mint ans = 0; rep(i,n+1) { ans += dp[i][i]; //mout(ans); } mout(ans); } int main(){ fast_io(); int t = 1; //cin >> t; while (t--) solve(); }