#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<int> tsolve(int p, vector<vector<int> > a, vector<int> ans) {
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 td = ans[r];
ans[r] = ans[s];
ans[s] = td;
int ip = minv(a[s][i], p);
for (int j = i; j < a[s].size(); j++) {
a[s][j] *= ip;
a[s][j] %= p;
}
ans[s] *= ip;
ans[s] %= 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;
}
ans[j] += p - (z*ans[s] % p);
ans[j] %= p;
}
s++;
}
vector<int> res = a[0];
for (int j = 0; j < res.size(); j++) {
res[j] = 0;
}
int pd = a.size() - 1;
for (int j = a.size(); j >= 0; j--) {
if (j == dr) {
res[j] = 0;
continue;
}
int s = 0;
for (int k = j + 1; k < res.size(); k++) {
s += res[k] * a[pd][k];
s %= p;
}
res[j] = (ans[pd] + p - s) % p;
pd--;
}
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);
vector<int> sp = tres[1];
vector<int> spb;
vector<vector<int> > qs;
for (int i = 0; i < a.size(); i++) {
vector<int> tb;
spb.push_back(0);
for (int j = 0; j < a[i].size(); j++) {
spb[i] += sp[j] * a[i][j];
tb.push_back(a[i][j] % p);
}
qs.push_back(tb);
}
for (int i = 0; i < spb.size(); i++) {
spb[i] /= spd;
spb[i] %= p;
spb[i] = p - spb[i];
spb[i] %= p;
}
vector<int> pres = tsolve(p, qs, spb);
for (int i = 0; i < pres.size(); i++) {
pres[i] = sp[i] + spd*pres[i];
pres[i] %= pd;
}
for (int i = 0; i < pd; i++) {
vector<int> t;
for (int j = 0; j < pres.size(); j++) {
t.push_back(pres[j] * i%pd);
}
res.push_back(t);
}
for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < a.size(); j++) {
int t = 0;
for (int k = 0; k < a[j].size(); k++) {
t += res[i][k] * a[j][k];
}
/* if (t%pd != 0) {
printf("WRONG:\n");
printf("res:");
for (int k = 0; k < a[j].size(); k++) {
printf("%d ", res[i][k]);
}
printf("\n");
printf("a:");
for (int k = 0; k < a[j].size(); k++) {
printf("%d ", a[j][k]);
}
printf("\n");
printf("%d\n", t%pd);
}*/
}
}
return res;
}
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");
}
}
Compilation message
PQ.c:1:17: fatal error: cstdio: No such file or directory
#include<cstdio>
^
compilation terminated.
