Div. 2 Codeforces Round #822 A-F( 二 ) _生活百科

時間復雜度 \(O(n^2)\)
空間復雜度 \(O(n^2)\)
代碼#include <bits/stdc++.h>#define ll long longusing namespace std;int a[357][357], b[357];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> b[i];for (int i = 1;i <= n;i++) {for (int j = 1;j <= n;j++) {a[i][j] = ((i * (j - i) + b[i]) % n + n) % n;}}for (int i = 1;i <= n;i++) {for (int j = 1;j <= n;j++) {cout << a[i][j] << ' ';}cout << '\n';}return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;//cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}F題解知識點：記憶化搜索，線性dp，數學，位運算。
先是一個結論：定義函數 \(parity(a)\) 表示 \(a\) 二進制位 \(1\) 的個數的奇偶性（奇數返回 \(1\) ，偶數返回 \(0\)），那么 \(S_i = parity(i)\)。
證明非常簡單：

由于 \(S\) 的生成方法是每次都從原來的一份取反得到 \(S'\) 放到 \(S\) 末尾，所以第 \(k(k\geq 1)\) 次擴展后 \(S\) 的編號一定是 \([0,2^{k-1}]\)。
對于第 \(k+1\) 次新生成的 \(S'\) 中的每一位編號 \(i'\)，滿足 \(i’ = i + 2^k\) ，因為編號 \(i\) 的第 \(k\) 位之前一定是 \(0\)，所以這次變換實際上是將編號 \(i\) 的第 \(k\) 位變為 \(1\) 作為編號 \(i'\) 。
顯然，所有數字都是從編號 \(0\) 開始數次變換得到的，每次變換都會將編號的一位 \(0\) 變為 \(1\)，因此我們記錄二進制 \(1\) 的數量就能得知這個編號從 \(0\) 變換了多少次。
\(S_0 = 0\) ，所以編號 \(i\) 有偶數個 \(1\) 就是變了偶數次，故 \(S_i=0\) ，否則 \(S_i = 1\)。即 \(S_i = parity(i)\)。

有了這個結論，我們就可以對問題進行量化。記原問題答案為 \(f(n,m)\)，有 \(f(n,m) = \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\)。
當 \(m = 0\) 時，顯然有 \(f(n,0) = 0\)。
當 \(m\) 為奇數時，先對末尾判斷再對 \(m-1\) 討論（偶數討論方便一點），有 \(f(n,m) = f(n,m-1) + [parity(i) \neq parity(n+i)]\)。
當 \(m\) 為偶數時：

\(n\) 為偶數，有如下關系：
\[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(2k+1) \neq parity(n+2k+1)\\\end{aligned}\]因為偶數末尾總是 \(0\) ，加 \(1\) 不會影響其余的二進制位，所以 \(1\) 的數量明確加 \(1\) ，奇偶性一定同時改變。
\[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(k) \neq parity(\frac{n}{2}+k)\end{aligned}\]因為偶數末尾總是 \(0\)，刪去這個 \(0\) 后，數字奇偶性不變。
那么有如下公式：
\[\begin{aligned} f(n,m) &= \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\\ &= 2\sum_{k = 0}^{\frac{m}{2}-1} [parity(2k) \neq parity(n+2k)]\\ &= 2\sum_{k = 0}^{\frac{m}{2}-1} [parity(k) \neq parity(\frac{n}{2}+k)]\\ &= 2f(\frac{n}{2},\frac{m}{2})\end{aligned}\]
\(n\) 為奇數，有如下關系：
\[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(2k) = parity(n+2k-1)\\ &\Leftrightarrow& &parity(k) = parity(\frac{n-1}{2}+k)\\\end{aligned}\]以及，
\[\begin{aligned} && &parity(2k+1) \neq parity(n+2k+1) \\ &\Leftrightarrow& &parity(2k) = parity(n+2k+1)\\ &\Leftrightarrow& &parity(k) = parity(\frac{n+1}{2}+k)\\\end{aligned}\]證明同上。
\[\begin{aligned} f(n,m) &= \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\\ &= \sum_{k = 0}^{\frac{m}{2}-1} ([parity(2k) = parity(n+2k-1)] + [parity(2k) = parity(n+2k+1)])\\ &= \sum_{k = 0}^{\frac{m}{2}-1} ([parity(k) = parity(\frac{n-1}{2}+k)] + [parity(k) = parity(\frac{n+1}{2}+k)])\\ &= m - f(\frac{n-1}{2},\frac{m}{2}) - f(\frac{n+1}{2},\frac{m}{2})\end{aligned}\]

至此，我們就可以通過記憶化搜索進行求解了。
時間復雜度 \(O(\log n \log m)\)
空間復雜度 \(O(\log n \log m)\)
代碼

#include <bits/stdc++.h>#define ll long longusing namespace std;bool check(ll a, ll b) {return __builtin_parityll(a) != __builtin_parityll(b);}map<pair<ll, ll>, ll> mp;ll f(ll n, ll m) {if (m == 0) return 0;if (mp.count({ n,m })) return mp[{n, m}];if (m & 1) return mp[{n, m}] = f(n, m - 1) + check(m - 1, n + m - 1);if (n & 1) return mp[{n, m}] = m - f(n / 2, m / 2) - f((n + 1) / 2, m / 2);else return mp[{n, m}] = 2 * f(n / 2, m / 2);}bool solve() {ll n, m;cin >> n >> m;cout << f(n, m) << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}