Submission #22671

#	Time	Username	Problem	Language	Result	Execution time	Memory
22671		↓우리보다잘하는팀 (#40)	Polynomial Quine (KRIII5_PQ)	C++98	2 / 7	79 ms	3308 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<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");
	}
}

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<std::vector<int> > pnsolve(int, int, std::vector<std::vector<int> >)':
PQ.cpp:79:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                    ^
PQ.cpp:81:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a[i].size(); j++) {
                     ^
PQ.cpp: In function 'std::vector<std::vector<int> > crtsolve(int, int, std::vector<std::vector<int> >)':
PQ.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                    ^
PQ.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < a[i].size(); j++) {
                     ^
PQ.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < resa.size(); i++) {
                    ^
PQ.cpp:128: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:143: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:125: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: 0 / 5