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

E题解知识点：构造，数学。
注意到，
\[\begin{aligned} & & a_{i_1,j_1} + a_{i_2,j_2} \not \equiv a_{i_1,j_2} + a_{i_2,j_1} \pmod n\\ &\Leftrightarrow & a_{i_2,j_2} - a_{i_2,j_1} \not \equiv a_{i_1,j_2} - a_{i_1,j_1} \pmod n\end{aligned}\]猜测一行元素具有线性关系，设 \(i_1\) 行线性系数为 \(k_1\) ， \(i_2\) 行线性系数为 \(k_2\) ，于是有：
\[\begin{aligned} &\Leftrightarrow & (j_2-j_1)\cdot k_2 \not \equiv (j_2-j_1)\cdot k_1 \pmod n\end{aligned}\]根据定理：当 \(k > 0\) 时,若 \(kx \equiv ky \pmod n\) ，则 \(x \equiv y\pmod {\frac{n}{gcd(k,n)}}\)。
于是有：
\[\begin{aligned} &\Leftrightarrow & k_2 \not \equivk_1 \pmod n\end{aligned}\]因此，只要每行之间的线性系数在 \(\mod n\) 意义下不同余，且在 \((i,i)\) 处经过 \(b_i\) 即可。
显然， \(i \in [1,n]\) 时即能保证互不同余，可以当作系数，因此有公式 \(b_{i,j} = (i \cdot (j-i) + b_i) \mod n\)。
时间复杂度 \(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\) 为偶数时：