C++の練習を兼ねて, AtCoder Regular Contest 151 の 問題D (Binary Representations and Queries) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 解説にあるように, 行列の積を, 事前に計算しておくロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 151 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題D/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 解き直し. // https://atcoder.jp/contests/arc151/editorial/5029 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<int, int>; using vp = vector<P>; using vl = vector<LL>; using vvl = vector<vl>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define a first #define b second const LL MOD = 998244353; LL a[1 << 18]; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); int n = 1 << N; rep(i, n) scanf("%lld", &a[i]); vp v(Q); rep(i, Q) scanf("%d %d", &v[i].a, &v[i].b); // 2. 事前計算(行列の積). // -> X[i] が, 0 ~ N - 1 に, わたって計算. vl eMatrix = {1, 0, 0, 1}; vvl qMatrix(N, eMatrix); rep(i, Q){ // クエリ情報. int x = v[i].a; int y = v[i].b; vl cur = qMatrix[x]; // y = 0. if(y == 0) qMatrix[x] = {cur[0], cur[1], (cur[0] + cur[2]) % MOD, (cur[1] + cur[3]) % MOD}; // y = 1. if(y == 1) qMatrix[x] = {(cur[0] + cur[2]) % MOD, (cur[1] + cur[3]) % MOD, cur[2], cur[3]}; } /* rep(i, N){ vl cur = qMatrix[i]; printf("i=%d m00=%lld m01=%lld m10=%lld m11=%lld\n", i, cur[0], cur[1], cur[2], cur[3]); } */ // 3. 整数列更新. // ex. N = 5 // b[i] = 1 は, b[i] = 0 と, [加算される側], [加算する側] を 入れ替えたものと見ることができる. // また, 以下のように, [加算される側], [加算する側] が, 対応するインデックス が, 動的に変わることに注意. // // b[0] = 0 // [加算される側] 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 // [加算する側] 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 // // b[1] = 0 // [加算される側] 2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31 // [加算する側] 0 1 4 5 8 9 12 13 16 17 20 21 24 25 28 29 // // b[2] = 0 // [加算される側] 4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31 // [加算する側] 0 1 2 3 8 9 10 11 16 17 18 19 24 25 26 27 // // b[3] = 0 // [加算される側] 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31 // [加算する側] 0 1 2 3 4 5 6 7 16 17 18 19 20 21 22 23 // // b[4] = 0 // [加算される側] 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 // [加算する側] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 rep(i, N){ vl cur = qMatrix[i]; int u = 1 << i; int v = 1 << (i + 1); repex(j, 0, 1 << N, v){ repx(k, j, j + u){ // 更新前情報. LL p = a[k + 0]; LL q = a[k + u]; // 更新. a[k + 0] = cur[0] * p % MOD + cur[1] * q % MOD; a[k + 0] %= MOD; a[k + u] = cur[2] * p % MOD + cur[3] * q % MOD; a[k + u] %= MOD; } } } // 4. 出力. rep(i, n) printf("%lld%s", a[i], (i < n - 1) ? " " : "\n"); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
[入力例] 2 2 0 1 2 3 1 1 0 0 [出力例] 2 6 2 5 ※AtCoderのテストケースより [入力例] 3 10 606248357 338306877 919152167 981537317 808873985 845549408 680941783 921035119 1 1 0 0 0 0 0 0 0 1 0 1 0 1 2 0 2 0 2 0 [出力例] 246895115 904824001 157201385 744260759 973709546 964549010 61683812 205420980 ※AtCoderのテストケースより [入力例] 3 6 3 1 4 1 5 9 2 6 2 1 2 0 1 1 1 0 0 0 0 1 [出力例] 45 31 64 44 74 53 103 74 [入力例] 5 15 2 2 3 6 0 6 7 9 7 7 4 9 9 7 8 9 6 9 6 4 0 9 1 7 3 6 6 8 7 3 1 2 2 0 2 1 1 1 1 0 0 1 0 1 0 0 2 1 0 1 4 0 3 1 2 1 2 0 3 0 3 1 [出力例] 3184 1837 5011 2896 4110 2371 6469 3738 1967 1134 3078 1778 2538 1463 3972 2294 5813 3358 8850 5116 7468 4314 11367 6571 3519 2031 5357 3095 4519 2608 6877 3973 [入力例] 7 50 105 65 84 96 44 84 114 29 101 85 107 16 63 39 64 62 54 59 56 7 69 92 0 58 78 113 8 11 108 79 84 122 11 63 94 92 51 46 14 81 105 0 72 53 98 100 50 27 28 60 72 30 107 86 19 33 84 19 17 120 109 72 64 7 24 75 14 63 1 61 37 70 76 85 59 37 68 109 74 85 49 64 73 100 43 94 51 38 72 1 32 38 114 91 56 39 102 35 90 30 81 76 71 78 29 88 79 64 77 52 121 31 75 35 5 73 66 47 32 116 112 98 88 75 16 24 52 103 6 1 1 0 3 0 2 0 2 1 5 1 6 0 2 1 1 0 4 1 0 1 4 1 2 0 2 1 4 1 0 1 5 1 3 1 1 1 3 0 5 0 1 0 1 1 6 1 4 1 0 0 2 1 4 0 3 0 0 0 6 1 5 1 6 1 6 1 0 0 3 1 0 0 5 1 3 0 6 1 3 1 3 0 6 0 5 0 3 0 3 0 0 1 0 1 6 1 0 1 [出力例] 88126790 240381482 51552281 514638308 199195645 774400092 760294249 401546881 224524928 209170759 489420394 672773238 325941805 717801442 201192366 727200754 676636858 279821546 243421329 811652115 627978707 526795799 306734163 879102198 167523305 618940189 721262090 387830206 153879606 450491377 816147042 465892088 104067306 958020824 695998303 880303207 628528832 146604919 579397171 274187367 882939691 720758794 269733526 271369651 422318169 699671401 442707565 896791957 86802880 738611319 411364892 649523406 939815836 171597330 686215793 925185833 521955928 822365926 34939833 697552625 455694697 424588556 99048474 267439342 884153389 534676791 378779225 521054823 593340723 40891658 195186633 298007808 985259095 113237189 346140098 795537288 958720177 415020808 243844755 716897207 446815658 636927490 644378123 222952753 906040118 446638787 30957510 556145792 927383936 118872216 579408946 344748640 730764997 891043707 279476482 656587924 380244244 544902818 511376758 799676718 987314293 780733555 717961322 768764675 586045102 416848955 362597359 443760755 660168846 108472957 779184020 430884266 235987825 48581070 600351802 755874351 777846243 335584921 856640682 122411711 228945524 876436615 586470034 916963377 165535763 121637992 917180332 711225132 |
■参照サイト
AtCoder Regular Contest 151