C++の練習を兼ねて, AtCoder Beginner Contest 199 の 問題F (Graph Smoothing) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, 実装して, AC版に到達できたと思う.
2. 個人的には, 操作後の頂点に書かれている数の期待値が, 行列計算から, 算出できるというロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 199 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F/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 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
// 解き直し. // https://atcoder.jp/contests/abc199/editorial/1167 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using vl = vector<LL>; using vvi = vector<vi>; 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 pb push_back const LL MOD = 1e9 + 7; LL a[111]; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t; } // 行列乗算を行う. // @param a: 行列. // @param b: 行列. // @return: 計算結果(mod版). vvl matrixMultiplication(vvl &a, vvl &b){ int n = a.size(); vvl ret(n, vl(n, 0LL)); rep(i, n){ rep(j, n){ LL t = 0; rep(k, n){ t += a[i][k] * b[k][j]; t %= MOD; } ret[i][j] = t; } } return ret; } int main(){ // 1. 入力情報. int N, M; LL K; scanf("%d %d %lld", &N, &M, &K); rep(i, N) scanf("%lld", &a[i]); vvi G(N); rep(i, M){ int x, y; scanf("%d %d", &x, &y); x--, y--; G[x].pb(y); G[y].pb(x); } // 2. 逆数. LL im = mPow((LL)M, MOD - 2); LL i2 = mPow(2LL, MOD - 2); // 3. 行列 m. vvl matrix(N, vl(N, 0LL)); rep(i, N){ // 3-1. 頂点 i の 次数. LL d = (LL)G[i].size(); // 3-2. (i, i)成分. // -> 1 - (d / M) * (1 / 2) を 設定. matrix[i][i] = (1 + (MOD - d) * im % MOD * i2 % MOD) % MOD; // 3-3. 頂点 i の 隣接頂点. // -> (1 / M) * (1 / 2) を 設定. for(auto &p : G[i]) matrix[p][i] = im * i2 % MOD; } // 4. 行列のべき乗. auto f = [&](vvl &m, LL b) -> vvl { // 4-1. 単位行列. vvl t(N, vl(N, 0LL)); rep(i, N) t[i][i] = 1; // 4-2. べき乗計算. vvl a = m; while(b){ if(b & 1) t = matrixMultiplication(t, a); a = matrixMultiplication(a, a); b >>= 1; } // 4-3. 返却. return t; }; // 5. 行列 m の K 乗. vvl kMatrix = f(matrix, K); // 6. 出力. rep(i, N){ LL ans = 0; rep(j, N){ ans += a[j] * kMatrix[j][i]; ans %= MOD; } printf("%lld\n", ans); } 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 120 121 122 123 124 125 126 127 128 129 130 |
[入力例] 3 2 1 3 1 5 1 2 1 3 [出力例] 3 500000005 500000008 ※AtCoderテストケースより [入力例] 3 2 2 12 48 36 1 2 1 3 [出力例] 750000036 36 250000031 ※AtCoderテストケースより [入力例] 4 5 1000 578 173 489 910 1 2 2 3 3 4 4 1 1 3 [出力例] 201113830 45921509 67803140 685163678 ※AtCoderテストケースより [入力例] 3 3 2 4 8 16 1 2 2 3 3 1 [出力例] 8 9 11 [入力例] 10 12 15 3 1 4 1 5 9 2 6 5 3 1 2 2 3 3 1 4 5 5 6 6 4 7 8 8 9 9 7 2 10 4 10 9 10 [出力例] 60105104 306664487 204426177 528008430 119334530 696618822 438064470 15348755 686133158 945296134 [入力例] 20 25 123456789 1 2 5 9 9 2 1 0 4 9 8 9 4 8 7 3 1 6 4 7 1 2 2 3 3 4 4 5 5 1 6 1 7 2 8 3 9 4 10 5 6 11 11 16 16 6 7 12 12 17 17 7 8 13 13 18 18 8 9 14 14 19 19 9 10 15 15 20 20 10 [出力例] 256833840 773912707 782215323 520721643 812754100 686558120 158488543 731923937 956199888 385308127 166469694 793620776 525611593 975959465 25353523 820154314 839516161 264137745 498907154 25353523 |