1716.md (5817B)
1 Source: https://codeforces.com/blog/entry/105653 2 3 [1716A - 2-3 Moves](/contest/1716/problem/A "Educational Codeforces Round 133 (Rated for Div. 2)") 4 5 Idea: [vovuh](/profile/vovuh "Master vovuh") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (vovuh)** 12 13 ``` 14 for _ in range(int(input())): 15 n = int(input()) 16 print(1 + (n == 1) if n <= 3 else (n + 2) // 3) 17 ``` 18 19 [1716B - Permutation Chain](/contest/1716/problem/B "Educational Codeforces Round 133 (Rated for Div. 2)") 20 21 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 22 23 **Tutorial** 24 25 Tutorial is loading... 26 27 **Solution (awoo)** 28 29 ``` 30 for _ in range(int(input())): 31 n = int(input()) 32 p = [i + 1 for i in range(n)] 33 print(n) 34 for i in range(n): 35 print(*p) 36 if i < n - 1: 37 p[i], p[i + 1] = p[i + 1], p[i] 38 ``` 39 40 [1716C - Robot in a Hallway](/contest/1716/problem/C "Educational Codeforces Round 133 (Rated for Div. 2)") 41 42 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 43 44 **Tutorial** 45 46 Tutorial is loading... 47 48 **Solution (awoo)** 49 50 ``` 51 INF = 2 * 10**9 52 53 for _ in range(int(input())): 54 m = int(input()) 55 a = [[int(x) for x in input().split()] for i in range(2)] 56 su = [[-INF for j in range(m + 1)] for i in range(2)] 57 for i in range(2): 58 for j in range(m - 1, -1, -1): 59 su[i][j] = max(su[i][j + 1] - 1, a[i][j], a[i ^ 1][j] - (2 * (m - j) - 1)) 60 pr = a[0][0] - 1 61 ans = INF 62 for j in range(m): 63 jj = j & 1 64 ans = min(ans, max(pr, su[jj][j + 1] - 2 * j - 1, a[jj ^ 1][j] - 2 * m + 1)) 65 pr = max(pr, a[jj ^ 1][j] - 2 * j - 1) 66 ans = min(ans, max(pr, su[jj ^ 1][j + 1] - 2 * j - 2)) 67 if j < m - 1: 68 pr = max(pr, a[jj ^ 1][j + 1] - 2 * j - 2) 69 print(ans + 2 * m) 70 ``` 71 72 [1716D - Chip Move](/contest/1716/problem/D "Educational Codeforces Round 133 (Rated for Div. 2)") 73 74 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 75 76 **Tutorial** 77 78 Tutorial is loading... 79 80 **Solution (Neon)** 81 82 ``` 83 #include <bits/stdc++.h> 84 85 using namespace std; 86 87 const int MOD = 998244353; 88 89 int main() { 90 int n, k; 91 cin >> n >> k; 92 vector<int> dp(n + 1), ans(n + 1); 93 dp[0] = 1; 94 for (int mn = 0; mn + k <= n; mn += k++) { 95 vector<int> sum(k); 96 for (int i = mn; i <= n; ++i) { 97 int cur = dp[i]; 98 dp[i] = sum[i % k]; 99 (sum[i % k] += cur) %= MOD; 100 (ans[i] += dp[i]) %= MOD; 101 } 102 } 103 for (int i = 1; i <= n; ++i) cout << ans[i] << ' '; 104 } 105 ``` 106 107 [1716E - Swap and Maximum Block](/contest/1716/problem/E "Educational Codeforces Round 133 (Rated for Div. 2)") 108 109 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 110 111 **Tutorial** 112 113 Tutorial is loading... 114 115 **Solution (BledDest)** 116 117 ``` 118 #include<bits/stdc++.h> 119 120 using namespace std; 121 const int K = 18; 122 123 struct node 124 { 125 long long sum, pref, suff, ans; 126 127 node(const node& l, const node& r) 128 { 129 sum = l.sum + r.sum; 130 pref = max(l.pref, l.sum + r.pref); 131 suff = max(r.suff, r.sum + l.suff); 132 ans = max(max(l.ans, r.ans), l.suff + r.pref); 133 } 134 135 node(int x) 136 { 137 sum = x; 138 pref = suff = ans = max(x, 0); 139 } 140 141 node() {}; 142 }; 143 144 int a[1 << K]; 145 vector<node> tree[2 << K]; 146 147 void build(int v, int l, int r) 148 { 149 tree[v].resize(r - l); 150 if(l == r - 1) 151 { 152 tree[v][0] = node(a[l]); 153 } 154 else 155 { 156 int m = (l + r) / 2; 157 build(v * 2 + 1, l, m); 158 build(v * 2 + 2, m, r); 159 for(int i = 0; i < m - l; i++) 160 { 161 tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]); 162 tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]); 163 } 164 } 165 } 166 167 int main() 168 { 169 int n; 170 scanf("%d", &n); 171 int m = (1 << n); 172 for(int i = 0; i < m; i++) 173 { 174 scanf("%d", &a[i]); 175 } 176 build(0, 0, m); 177 int q; 178 scanf("%d", &q); 179 int cur = 0; 180 for(int i = 0; i < q; i++) 181 { 182 int x; 183 scanf("%d", &x); 184 cur ^= (1 << x); 185 printf("%lld\n", tree[0][cur].ans); 186 } 187 } 188 ``` 189 190 [1716F - Bags with Balls](/contest/1716/problem/F "Educational Codeforces Round 133 (Rated for Div. 2)") 191 192 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 193 194 **Tutorial** 195 196 Tutorial is loading... 197 198 **Solution (BledDest)** 199 200 ``` 201 #include<bits/stdc++.h> 202 203 using namespace std; 204 205 const int MOD = 998244353; 206 const int N = 2043; 207 208 int dp[N][N]; 209 210 int add(int x, int y) 211 { 212 x += y; 213 while(x >= MOD) x -= MOD; 214 while(x < 0) x += MOD; 215 return x; 216 } 217 218 int sub(int x, int y) 219 { 220 return add(x, -y); 221 } 222 223 int mul(int x, int y) 224 { 225 return (x * 1ll * y) % MOD; 226 } 227 228 int binpow(int x, int y) 229 { 230 int z = 1; 231 while(y > 0) 232 { 233 if(y % 2 == 1) z = mul(z, x); 234 x = mul(x, x); 235 y /= 2; 236 } 237 return z; 238 } 239 240 int inv(int x) 241 { 242 return binpow(x, MOD - 2); 243 } 244 245 int divide(int x, int y) 246 { 247 return mul(x, inv(y)); 248 } 249 250 void precalc() 251 { 252 dp[1][1] = 1; 253 for(int i = 1; i < N - 1; i++) 254 for(int j = 1; j <= i; j++) 255 { 256 dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j)); 257 dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]); 258 } 259 } 260 261 int solve(int n, int m, int k) 262 { 263 int way1 = (m / 2) + (m % 2); 264 int curA = n; 265 int ans = 0; 266 int ways_chosen = way1; 267 int ways_other = binpow(m, n - 1); 268 int invm = inv(m); 269 for(int i = 1; i <= k; i++) 270 { 271 ans = add(ans, mul(mul(curA, dp[k][i]), mul(ways_chosen, ways_other))); 272 curA = mul(curA, sub(n, i)); 273 ways_chosen = mul(way1, ways_chosen); 274 ways_other = mul(ways_other, invm); 275 } 276 return ans; 277 } 278 279 int main() 280 { 281 int t; 282 cin >> t; 283 precalc(); 284 for(int i = 0; i < t; i++) 285 { 286 int n, m, k; 287 cin >> n >> m >> k; 288 cout << solve(n, m, k) << endl; 289 } 290 } 291 ```