#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;
^
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
