結果
問題 | No.2874 Gunegune Tree |
ユーザー | syun0713 |
提出日時 | 2024-09-06 23:31:27 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 916 ms / 2,000 ms |
コード長 | 9,073 bytes |
コンパイル時間 | 5,161 ms |
コンパイル使用メモリ | 286,532 KB |
実行使用メモリ | 17,416 KB |
最終ジャッジ日時 | 2024-09-06 23:31:46 |
合計ジャッジ時間 | 18,298 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 1 ms
6,944 KB |
testcase_03 | AC | 65 ms
6,940 KB |
testcase_04 | AC | 375 ms
9,088 KB |
testcase_05 | AC | 135 ms
6,940 KB |
testcase_06 | AC | 3 ms
6,944 KB |
testcase_07 | AC | 871 ms
16,528 KB |
testcase_08 | AC | 404 ms
9,472 KB |
testcase_09 | AC | 39 ms
6,940 KB |
testcase_10 | AC | 740 ms
14,292 KB |
testcase_11 | AC | 568 ms
12,088 KB |
testcase_12 | AC | 176 ms
6,944 KB |
testcase_13 | AC | 867 ms
16,324 KB |
testcase_14 | AC | 691 ms
13,952 KB |
testcase_15 | AC | 118 ms
6,940 KB |
testcase_16 | AC | 877 ms
16,840 KB |
testcase_17 | AC | 99 ms
6,940 KB |
testcase_18 | AC | 108 ms
6,940 KB |
testcase_19 | AC | 73 ms
6,944 KB |
testcase_20 | AC | 95 ms
6,940 KB |
testcase_21 | AC | 285 ms
7,808 KB |
testcase_22 | AC | 424 ms
9,900 KB |
testcase_23 | AC | 267 ms
7,552 KB |
testcase_24 | AC | 354 ms
8,832 KB |
testcase_25 | AC | 607 ms
12,688 KB |
testcase_26 | AC | 397 ms
9,088 KB |
testcase_27 | AC | 859 ms
16,716 KB |
testcase_28 | AC | 198 ms
6,940 KB |
testcase_29 | AC | 528 ms
11,008 KB |
testcase_30 | AC | 395 ms
9,472 KB |
testcase_31 | AC | 296 ms
7,936 KB |
testcase_32 | AC | 916 ms
17,416 KB |
コンパイルメッセージ
main.cpp:75:21: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 75 | void ain(set<T>& Y, auto n) { | ^~~~ main.cpp:82:26: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts' 82 | void ain(multiset<T>& Y, auto n) { | ^~~~
ソースコード
/*#pragma GCC target("arch=skylake-avx512") #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops")*/ #include<bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; istream& operator>>(istream& is, mint& a) { long long v; is >> v; a = v; return is; } ostream& operator<<(ostream& os, mint& a) { return os << a.val(); } #endif using namespace std; template<typename T> using vec = vector<T>; using ll = long long; using ull = unsigned long long; using vi = vec<int>; using vs = vec<string>; using si = set<int>; using sll = set<ll>; using vc = vec<char>; using vvi = vec<vi>; using vll = vec<ll>; using vvll = vec<vll>; using vsi = vec<si>; using vsll = vec<sll>; using vd = vec<double>; using vvd = vec<vd>; using pii = pair<int, int>; using pll = pair<ll, ll>; using mii = map<int, int>; using mll = map<ll, ll>; using msi = map<string, int>; using vpii = vec<pii>; using vpll = vec<pll>; using spii = set<pii>; using spll = set<pll>; using vb = vector<bool>; using vvb = vector<vb>; #define rep(i,j,n) for(ll i=j;i<n;i++) #define rrep(i,j,n) for (ll i = n-1; i >=j; i--) #define rp(i,n) rep(i,0,n) #define rrp(i,n) rrep(i,0,n) #define all(v) v.begin(), v.end() #define pb push_back #define ins insert #define yes cout<<"Yes"<<endl; #define no cout<<"No"<<endl; #define yn(jg) cout<<(jg? "Yes":"No")<<endl; #define NL {cout<<endl;} #define n0 {cout<<"-1"<<endl;} #define lwb lower_bound #define upb upper_bound #define sz size() #define fi first #define se second #define nxp next_permutation ll mod0 = 998244353, lmax = 2e18, inf = 2e9; double pi = 3.141592653589793238462643; vll vh = { 998244353, 998244853, 1000000007, 1000000009, 1012924417 }; template<typename... T> void in(T&... X) { (cin >> ... >> X); } template<typename T> void ain(vec<T>& Y) { rp(K, Y.size()) cin >> Y[K]; } template<typename T> void ain(set<T>& Y, auto n) { rp(i, n) { T YY; cin >> YY; Y.insert(YY); } } template<typename T> void ain(multiset<T>& Y, auto n) { rp(i, n) { T YY; cin >> YY; Y.insert(YY); } } template<typename T> void bin(vec<vec<T>>& Z) { rp(L, Z.size()) ain(Z[L]); } template<typename T> void aout(T& a) { for (auto I : a) cout << I << " "; cout << endl; } void aout(pll a) { cout << a.fi << " " << a.se << endl; } template<typename T> void aout(queue<T> a) { while (!a.empty()) { cout << a.front(); a.pop(); } } template<typename T> void aout(stack<T> a) { while (!a.empty()) { cout << a.top(); a.pop(); } } #define bout(a) {for(auto J:a) aout(J);} template<typename T> bool chmin(T& M1, T M2) { if (M1 > M2) { M1 = M2; return 1; } else return 0; } template<typename T> bool chmax(T& M1, T M2) { if (M1 < M2) { M1 = M2; return 1; } else return 0; } template<typename T> auto vmax(T& a) { return *max_element(all(a)); } template<typename T> auto vmin(T& a) { return *min_element(all(a)); } template<typename T> auto vmaxi(T& a) { return max_element(all(a)) - a.begin(); } template<typename T> auto vmini(T& a) { return min_element(all(a)) - a.begin(); } vector<pair<char, ll>> rle(string rr) { vector<pair<char, ll>> ret; char lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } vector<pair<int, ll>> rle(vi rr) { vector<pair<int, ll>> ret; int lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } vector<pair<ll, ll>> rle(vll rr) { vector<pair<ll, ll>> ret; ll lc; rep(i, 0, rr.size()) { if (i > 0 && rr[i] == lc) ret[ret.sz - 1].second++; else { ret.pb({ rr[i],1 }); } lc = rr[i]; } return ret; } template<typename T> auto lwa(vector<T>& a, T b) {//aでbより小さい最大の値のイテレータ(複数あれば右端) auto i = lwb(all(a), b); if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwa(set<T>& a, T b) {//aでbより小さい最大の値のイテレータ auto i = a.lwb(b); if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwa(multiset<T>& a, T b) {//aでbより小さい最大の値のイテレータ auto i = a.lwb(b); if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwc(vector<T>& a, T b) {//aでb以下の最大の値のイテレータ(複数あれば左端) auto i = lwb(all(a), b); if (i != a.end() && *i == b) return i; if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwc(set<T>& a, T b) {//aでb以下の最大の値のイテレータ auto i = a.lwb(b); if (i != a.end() && *i == b) return i; if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> auto lwc(multiset<T>& a, T b) {//aでb以下の最大の値のイテレータ auto i = a.lwb(b); if (i != a.end() && *i == b) return i; if (i == a.begin()) return a.end(); else i--; return i; } template<typename T> vec<T> rsw(vec<T>& a) {//累積和 vec<T> b = a; rep(i, 1, b.size()) b[i] += b[i - 1]; return b; } bool kai(string S) {//回文か判定 bool ans = 1; rp(i, S.size()) if (S[i] != S[S.size() - 1 - i]) ans = 0; return ans; } sll yk(ll n) {//約数全列挙O(sqrt(N)),set<int> sll yaku; for (ll i = 1; i * i <= n; i++) if (n % i == 0) { yaku.insert(i); yaku.insert(n / i); } return yaku; } vi ssa(int n) {//n:必要な素数の最大値 素数全列挙 vector<int> prime; vector<int>lpf(n + 1, 0); rep(i, 2, n + 1) { if (lpf[i] == 0) { lpf[i] = i; prime.push_back(i); } for (int k : prime) { if (k * i > n || k > lpf[i]) break;//k最小素因数よりk<=i lpf[k * i] = k;//kを最小素因数に持つ数k*iを拾う } } return prime; } vector<pll> sib(ll x) {//素因数分解 if (x == 1) return vector<pll>(1, { 1,1 }); vector<pll> ans; for (ll i = 2; i * i <= x; i++) {//rootx回iを回しxで割る ll kaisu = 0; while (x % i == 0) { x /= i; kaisu++; } if (kaisu > 0) ans.pb({ i,kaisu }); } if (x != 1) ans.pb({ x,1 }); return ans; } template<typename T> vec<T> zat(vec<T> a) {//座標圧縮 auto b = a; sort(all(b)); b.erase(unique(all(b)), b.end()); vec<T> c(a.size()); rp(i, a.size()) { c[i] = lwb(all(b), a[i]) - b.begin(); } return c; } template<typename T> void cp(map < T, ll >& a, T b, ll c) {//countplus if (a.find(b) == a.end()) a[b] = c; else a[b] += c; if (a[b] == 0) a.erase(b); } template<typename T> vec<T> inv(vec<T> a) {//0-indexed 逆関数(1-indexedは全要素--) vec<T> ans(a.sz); rp(i, a.sz) { ans[a[i]] = i; } return ans; } vll hs(string s) {//hash vll r = { 0,0,0,0,0 }; rp(i, 5) { rp(j, s.sz) { r[i] *= 27; r[i] += (s[j] - 'a' + 1); r[i] %= vh[i]; } } return r; } vll hsp(ll n) {//hashpow vll r = { 1,1,1,1,1 }; rp(i, 5) { rp(j, n) { r[i] *= 27; r[i] %= vh[i]; } } return r; } template<typename T> bool cross(T a, T b, T c, T d) {//区間(a,b)と区間(c,d)が重なるか判定 return !(b <= c || d <= a); } template<typename T> bool crosse(T a, T b, T c, T d) {//区間[a,b]と区間[c,d]が重なるか判定 return !(b < c || d < a); } //lazy_segtree<S, op, e, F, mapping, composition, id> seg(n); //S:中身型 op:左右合成 e:初期値 //F:遅延型 mapping:遅延適用後の要素 composition:遅延合成( 関数f(g()) ) id:遅延初期値(何もさせない) using S = int; using F = int; S op(S a,S b) { return a+b; } S e() { return 0; }/* S mapping(F x, S a) {//xをaに作用(x初期値に注意) if (x != 0)return x; else return a; } F composition(F f, F g) {//fの方が後(f初期値に注意) if (f != 0)return f; else return g; } F id() {return 0;}*/ //cout<<setprecision(15)<<fixed<< //function<返り値の型(引数の型1, 引数の型2, ...)> 関数名 = [&](引数の型1 引数名1, 引数の型2, 引数名2, ...) int main() { int n; cin >> n; vec<vec<pair<mint, mint>>> dp(n + 1, vec<pair<mint, mint>>(5, { 0,0 })); dp[1][0] = { 0,mint(1)/5 }; dp[1][1] = { 1,mint(1) / 5 }; dp[1][2] = { 1,mint(1) / 5 }; dp[1][3] = { 1,mint(1) / 5 }; dp[1][4] = { 0,mint(1) / 5 }; rep(i, 2, n+1) rp(j, 5) { rp(k, 5) { if (j == 0 || j == 4) { if (abs(j - k) <= 1) { if (k == 0 || k == 4) { dp[i][j].fi += dp[i - 1][k].fi * dp[i - 1][k].se / 2; dp[i][j].se += dp[i - 1][k].se / 2; } else { dp[i][j].fi += ( dp[i - 1][k].fi) * dp[i - 1][k].se / 3; dp[i][j].se += dp[i - 1][k].se / 3; } } } else { if (abs(j - k) <= 1) { if (k == 0 || k == 4) { dp[i][j].fi += (dp[i - 1][k].fi + 1) * dp[i - 1][k].se / 2; dp[i][j].se += dp[i - 1][k].se / 2; } else { dp[i][j].fi += (dp[i - 1][k].fi+1) * dp[i - 1][k].se / 3; dp[i][j].se += dp[i - 1][k].se / 3; } } } } if (dp[i][j].se != 0) dp[i][j].fi /= dp[i][j].se; } mint ans = 0; rp(i, 5) ans += dp[n][i].fi * dp[n][i].se; //rp(i, 5) cout << dp[n][i].fi << " " << dp[n][i].se << endl; cout << ans << endl; }