Rectangular Congruence

原题链接

题意

构造一个 \(n\times n\) 的数组，满足以下要求：

• \(0\le a_{i,j}<n,\forall\ 1\le i,j\le n\) ;
• \(a_{r_1,c_1}+a_{r_2,c_2}\not\equiv a_{r_1,c_2}+a_{r_2,c_1}\pmod{n}\)，对于任意的 \(1\le r_1<r_2\le n,1\le c_1<c_2\le n\) ;
• \(a_{i,i}=b_i,\forall\ 1\le i\le n\) .

⭐rating: 2100

---

分析

观察到

\[ \begin{align} a_{r_1,c_1}+a_{r_2,c_2}\not\equiv a_{r_1,c_2}+a_{r_2,c_1}\pmod{n}\\ \iff a_{r_1,c_1}+a_{r_2,c_2}\not\equiv a_{r_1,c_2}+a_{r_2,c_1}\pmod{n}\\ \end{align} \]

构造每一行为公差不同的等差数列，根据式子每行都有 \(c_2-c_1\) 个元素，可以相互抵消，此时式子就变成了 \(d_{r_1}\not\equiv d_{r_2}\pmod{n}\)，由于每行公差都不同，那么必然不会出现同余的情况。令第 \(i\) 行的公差为 \(i-1\) 即可。

同时也要满足 \(a_{i,i}=b_i\) 的要求，因此通项公式 \(a_{i,j}=(j-i)\times(i-1)+b_i\)。此外还需要满足 \(0\le a_{i,j}<n\) 的要求，用模运算即可将其控制在 \([0,n)\) 的范围内。最终通项公式为：

\[a_{i,j}=(((j-i)\times(i-1)+b_i)\% n+n)\% n\]

时间复杂度为 \(O(n^2)\)。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;
        for (int j = 1; j <= n; j++) {
            cout << (((j - i) * (i - 1) + b) % n + n) % n << ' ';
        }
        cout << endl;
    }

    return 0;
}