Submission #23043

#	Time	Username	Problem	Language	Result	Execution time	Memory
23043		gs12117	Polynomial Quine (KRIII5_PQ)	C++98	7 / 7	126 ms	4632 KiB

PQ

#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);
                                                  ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5