Submission #22887

#	Time	Username	Problem	Language	Result	Execution time	Memory
22887		AcornCkiGs14004Team (#40)	Polynomial Quine (KRIII5_PQ)	C++14	2 / 7	56 ms	2156 KiB

PQ

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long lint;
const int MAXN = 100005;

int n;
vector<int> basis[205];
lint ans[205];

lint ipow(lint x, lint p){
	int mod = n;
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}
void upload(vector<int> &v){
	for(int i=0; i<n; i++){
		if(v[i] == 0) continue;
		if(basis[i].empty()){
			basis[i] = v;
			break;
		}
		int gyesu = v[i] * ipow(basis[i][i], n-2) % n;
		for(int j=0; j<n; j++){
			v[j] += n - gyesu * basis[i][j] % n;
			v[j] %= n;
		}
	}
}

int main(){
	cin >> n;
	for(int i=1; i<n; i++){
		vector<int> ws;
		ws.push_back(1);
		for(int j=1; j<n; j++){
			ws.push_back(ws.back() * i % n);
		}
		ws[i] += n - 1;
		ws[i] %= n;
		upload(ws);
	}
	int idp = -1;
	for(int i=0; i<n; i++){
		if(basis[i].empty()) idp = i;
	}
	assert(idp == n-1);
	for(int i=0; i<n; i++){
		ans[n-1] = i;
		for(int j=n-2; j>=0; j--){
			ans[j] = 0;
			for(int k=0; k<n; k++){
				ans[j] -= ans[k] * basis[j][k];
			}
			ans[j] %= n;
			ans[j] += n;
			ans[j] %= n;
			ans[j] *= ipow(basis[j][j], n-2);
			ans[j] %= n;
		}
		for(int i=n-1; i>=0; i--) printf("%lld ", ans[i]);
		puts("");
	}
}

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