oj.uz

답안 #22881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22881 2017-04-30T07:58:59 Z AcornCkiGs14004Team(#953, gs14004, cki86201, dotorya) Polynomial Quine (KRIII5_PQ) C++14
0 / 7
 0 ms 2024 KB 
#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(basis[i].empty()){
			basis[i] = v;
			break;
		}
		if(v[i] == 0) continue;
		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;
	}
	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("");
	}
}

Compilation message

PQ.cpp: In function 'int main()':
PQ.cpp:50:6: warning: variable 'idp' set but not used [-Wunused-but-set-variable]
  int idp = -1;
      ^

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Incorrect 0 ms 2024 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Incorrect 0 ms 2024 KB Output isn't correct
3 Halted 0 ms 0 KB -