# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22669 | ↓우리보다잘하는팀 (#40) | Polynomial Quine (KRIII5_PQ) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int _minv[210][210];
long long int mpow(int x, int y, int mod) {
if (y == 0)return 1;
long long int res = mpow(x, y / 2, mod);
res *= res;
res %= mod;
if (y % 2 == 1) {
res *= x;
res %= mod;
}
return res;
}
int minv(int x, int mod) {
if (_minv[mod][x] != 0)return _minv[mod][x];
return _minv[mod][x] = mpow(x, mod - 2, mod);
}
vector<vector<int>> solve(int p, vector<vector<int>> a) {
int s = 0;
int dr = -1;
for (int i = 0; i < a.size() + 1; i++) {
int flg, r;
flg = 0;
for (int j = s; j < a.size(); j++) {
if (a[j][i] != 0) {
flg = 1;
r = j;
break;
}
}
if (flg == 0) {
dr = i;
continue;
}
vector<int> t = a[r];
a[r] = a[s];
a[s] = t;
int ip = minv(a[s][i], p);
for (int j = i; j < a[s].size(); j++) {
a[s][j] *= ip;
a[s][j] %= p;
}
for (int j = s + 1; j < a.size(); j++) {
int z = a[j][i];
for (int k = i; k < a[j].size(); k++) {
a[j][k] += p - (z*a[s][k] % p);
a[j][k] %= p;
}
}
s++;
}
vector<vector<int>> res;
for (int i = 0; i < p; i++) {
vector<int> t = a[0];
for (int j = 0; j < t.size(); j++) {
t[j] = 0;
}
t[dr] = i;
for (int j = dr - 1; j >= 0; j--) {
int s=0;
for (int k = j + 1; k <= dr; k++) {
s += t[k] * a[j][k];
s %= p;
}
t[j] = (p - s) % p;
}
res.push_back(t);
}
return res;
}
vector<vector<int>> pnsolve(int p, int pd, vector<vector<int>> a) {
if (p == pd)return solve(p, a);
vector<vector<int>> res;
vector<vector<int>> b;
int spd = pd / p;
for (int i = 0; i < a.size(); i++) {
vector<int> tb;
for (int j = 0; j < a[i].size(); j++) {
tb.push_back(a[i][j] % spd);
}
b.push_back(tb);
}
vector<vector<int>> tres = pnsolve(p, spd, b);
// for (int i = 0; i < tres.size(); i++) {
// }
return tres;
}
vector<vector<int>> crtsolve(int n, int sn, vector<vector<int>> a) {
vector<vector<int>> res;
if (n == 1) {
vector<int> t;
for (int i = 0; i < sn; i++) {
t.push_back(0);
}
res.push_back(t);
return res;
}
int pdiv;
for (int i = 2; i <= n; i++) {
if (n%i == 0) {
pdiv = i;
break;
}
}
int pn = pdiv;
while (n % (pdiv*pn) == 0) {
pn *= pdiv;
}
int cn = n / pn;
vector<vector<int>> aa;
vector<vector<int>> ab;
for (int i = 0; i < a.size(); i++) {
vector<int> ta;
vector<int> tb;
for (int j = 0; j < a[i].size(); j++) {
ta.push_back(a[i][j] % pn);
tb.push_back(a[i][j] % cn);
}
aa.push_back(ta);
ab.push_back(tb);
}
vector<vector<int>> resa = pnsolve(pdiv, pn, aa);
vector<vector<int>> resb = crtsolve(cn, sn, ab);
for (int i = 0; i < resa.size(); i++) {
for (int j = 0; j < resb.size(); j++) {
vector<int> t;
for (int k = 0; k < sn; k++) {
int r = resa[i][k];
while (r%cn != resb[j][k])r += pn;
t.push_back(r);
}
res.push_back(t);
}
}
return res;
}
int main() {
int n;
vector<vector<int>> s;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
vector<int> t;
int r = 1;
for (int j = 0; j < n; j++) {
t.push_back(r);
r *= i;
r %= n;
}
t[i] += n - 1;
t[i] %= n;
vector<int> rt;
for (int j = n - 1; j >= 0; j--) {
rt.push_back(t[j]);
}
s.push_back(rt);
}
vector<vector<int>> res = crtsolve(n, n, s);
std::sort(res.begin(), res.end());
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", res[i][j]);
}
printf("\n");
}
}