Submission #23043

#TimeUsernameProblemLanguageResultExecution timeMemory
23043gs12117Polynomial Quine (KRIII5_PQ)C++98
7 / 7
126 ms4632 KiB
#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 (stderr)

PQ.cpp: In function 'std::vector<std::vector<int> > solve(int, std::vector<std::vector<int> >)':
PQ.cpp:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size() + 1; i++) {
                    ^
PQ.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = s; j < a.size(); j++) {
                     ^
PQ.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i; j < a[s].size(); j++) {
                     ^
PQ.cpp:46:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = s + 1; j < a.size(); j++) {
                         ^
PQ.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = i; k < a[j].size(); k++) {
                      ^
PQ.cpp:58:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < t.size(); j++) {
                     ^
PQ.cpp: In function 'std::vector<int> tsolve(int, std::vector<std::vector<int> >, std::vector<int>)':
PQ.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size() + 1; i++) {
                    ^
PQ.cpp:80:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = s; j < a.size(); j++) {
                     ^
PQ.cpp:98:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = i; j < a[s].size(); j++) {
                     ^
PQ.cpp:104:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = s + 1; j < a.size(); j++) {
                         ^
PQ.cpp:106:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = i; k < a[j].size(); k++) {
                      ^
PQ.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < res.size(); j++) {
                    ^
PQ.cpp:126:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int k = j + 1; k < res.size(); k++) {
                         ^
PQ.cpp: In function 'std::vector<std::vector<int> > pnsolve(int, int, std::vector<std::vector<int> >)':
PQ.cpp:140:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                    ^
PQ.cpp:142:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a[i].size(); j++) {
                     ^
PQ.cpp:151:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                    ^
PQ.cpp:154:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a[i].size(); j++) {
                     ^
PQ.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < spb.size(); i++) {
                    ^
PQ.cpp:167:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < pres.size(); i++) {
                    ^
PQ.cpp:173:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < pres.size(); j++) {
                     ^
PQ.cpp:178:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < res.size(); i++) {
                    ^
PQ.cpp:179:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a.size(); j++) {
                     ^
PQ.cpp:181:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < a[j].size(); k++) {
                      ^
PQ.cpp: In function 'std::vector<std::vector<int> > crtsolve(int, int, std::vector<std::vector<int> >)':
PQ.cpp:226:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                    ^
PQ.cpp:229:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a[i].size(); j++) {
                     ^
PQ.cpp:238:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < resa.size(); i++) {
                    ^
PQ.cpp:239:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < resb.size(); j++) {
                     ^
PQ.cpp: In function 'int main()':
PQ.cpp:254:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
PQ.cpp: In function 'std::vector<std::vector<int> > crtsolve(int, int, std::vector<std::vector<int> >)':
PQ.cpp:236:50: warning: 'pdiv' may be used uninitialized in this function [-Wmaybe-uninitialized]
  vector<vector<int> > resa = pnsolve(pdiv, pn, aa);
                                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...