結果
問題 | No.1697 Deque House |
ユーザー | chineristAC |
提出日時 | 2021-08-15 21:14:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 87 ms / 3,500 ms |
コード長 | 2,848 bytes |
コンパイル時間 | 13,158 ms |
コンパイル使用メモリ | 334,108 KB |
実行使用メモリ | 32,024 KB |
最終ジャッジ日時 | 2023-09-26 15:41:40 |
合計ジャッジ時間 | 15,239 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 6 ms
11,588 KB |
testcase_01 | AC | 6 ms
11,536 KB |
testcase_02 | AC | 6 ms
11,580 KB |
testcase_03 | AC | 6 ms
11,560 KB |
testcase_04 | AC | 6 ms
11,488 KB |
testcase_05 | AC | 6 ms
11,504 KB |
testcase_06 | AC | 6 ms
11,504 KB |
testcase_07 | AC | 7 ms
11,520 KB |
testcase_08 | AC | 6 ms
11,700 KB |
testcase_09 | AC | 84 ms
31,868 KB |
testcase_10 | AC | 45 ms
22,432 KB |
testcase_11 | AC | 48 ms
22,652 KB |
testcase_12 | AC | 37 ms
20,512 KB |
testcase_13 | AC | 21 ms
15,036 KB |
testcase_14 | AC | 31 ms
17,596 KB |
testcase_15 | AC | 53 ms
22,692 KB |
testcase_16 | AC | 52 ms
21,604 KB |
testcase_17 | AC | 31 ms
17,384 KB |
testcase_18 | AC | 35 ms
18,236 KB |
testcase_19 | AC | 33 ms
18,208 KB |
testcase_20 | AC | 87 ms
31,796 KB |
testcase_21 | AC | 87 ms
32,024 KB |
testcase_22 | AC | 86 ms
32,008 KB |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <algorithm> #include <cmath> #include <iomanip> #include <random> #include <stdio.h> #include <fstream> #include <functional> #include <cassert> #include <atcoder/all> #include "testlib.h" using namespace std; using namespace atcoder; #define rep(i,n,c) for (int i=0;i<n;i+=c) #define append push_back #define all(x) (x).begin(), (x).end() template<class T> using vec = vector<T>; template<class T> using vvec = vec<vec<T>>; template<class T> using vvvec = vec<vvec<T>>; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<class T> bool chmin(T &a, T b){ if (a>b){ a = b; return true; } return false; } template<class T> bool chmax(T &a, T b){ if (a<b){ a = b; return true; } return false; } template<class T> T sum(vec<T> x){ T res=0; for (auto e:x){ res += e; } return res; } template<class T> void printv(vec<T> x){ for (auto e:x){ cout<<e<<" "; } cout<<"\n"; } int pow(int n,int k){ int res = 1; while (k){ if (k&1){ res *= n; } n *= n; k >>= 1; } return res; } using mint = modint998244353; mint f[15][100001]; int main(int argc,char* argv[]){ registerValidation(argc,argv); int N = inf.readInt(2,1000000); inf.readSpace(); int K = inf.readInt(1,14); inf.readEoln(); vec<mint> A(N); int a; for (int i=0;i<N;i++){ a = inf.readInt(1,998244353-1); A[i] = (mint) a; if (i==N-1){ inf.readEoln(); } else{ inf.readSpace(); } } inf.readEof(); mint ans = 0; for (int j=0;j<N;j++){ f[0][j] = (mint)1; } mint t = 1; for (int i=1;i<=K;i++){ t *= (mint) 2; f[i][0] = (mint) 1; for (int j=1;j<=N;j++){ f[i][j] = t * f[i][j-1] + f[i-1][j]; } } auto calc_dp = [&](){ vec<vec<mint>> dp(N,vec<mint>(K+1,0)); mint t = 1; for (int j=0;j<=K;j++){ dp[0][j] = t; t = 2 * t * A[0]; } for (int i=1;i<N;i++){ dp[i][0] = dp[i-1][0]; for (int j=0;j<=K;j++){ dp[i][j] = dp[i-1][j] + dp[i][j-1]; } mint t0 = 1; mint t1 = 1; for (int j=0;j<=K;j++){ dp[i][j] = t0 * (f[j][i]*t1+dp[i][j]); t0 *= (mint) 2; t1 *= A[i]; } } return dp; }; auto dp = calc_dp(); mint c = 2; c = c.pow(K); for (int i=1;i<N;i++){ ans += (A[i].pow(K) * c * f[K][i-1] + dp[i-1][K]) * c * f[K-1][N-i-1]; } reverse(all(A)); auto rdp = calc_dp(); for (int i=1;i<N-1;i++){ for (int j=0;j<K;j++){ ans += rdp[i-1][j] * c * c * f[K][N-2-i]; } } mint i4 = 4; i4 = i4.inv(); ans *= i4.pow(K); cout<<ans.val()<<endl; }