#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("");
}
}
| # |
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 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 11 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 16 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 17 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 18 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 19 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 20 |
Correct |
3 ms |
2024 KB |
Output is correct |
| 21 |
Correct |
3 ms |
2024 KB |
Output is correct |
| 22 |
Correct |
3 ms |
2024 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2024 KB |
Output is correct |
| 24 |
Correct |
6 ms |
2024 KB |
Output is correct |
| 25 |
Correct |
6 ms |
2024 KB |
Output is correct |
| 26 |
Correct |
9 ms |
2024 KB |
Output is correct |
| 27 |
Correct |
9 ms |
2024 KB |
Output is correct |
| 28 |
Correct |
9 ms |
2024 KB |
Output is correct |
| 29 |
Correct |
9 ms |
2024 KB |
Output is correct |
| 30 |
Correct |
13 ms |
2156 KB |
Output is correct |
| 31 |
Correct |
16 ms |
2156 KB |
Output is correct |
| 32 |
Correct |
16 ms |
2156 KB |
Output is correct |
| 33 |
Correct |
16 ms |
2156 KB |
Output is correct |
| 34 |
Correct |
23 ms |
2156 KB |
Output is correct |
| 35 |
Correct |
23 ms |
2156 KB |
Output is correct |
| 36 |
Correct |
26 ms |
2156 KB |
Output is correct |
| 37 |
Correct |
33 ms |
2156 KB |
Output is correct |
| 38 |
Correct |
33 ms |
2156 KB |
Output is correct |
| 39 |
Correct |
33 ms |
2156 KB |
Output is correct |
| 40 |
Correct |
39 ms |
2156 KB |
Output is correct |
| 41 |
Correct |
43 ms |
2156 KB |
Output is correct |
| 42 |
Correct |
43 ms |
2156 KB |
Output is correct |
| 43 |
Correct |
49 ms |
2156 KB |
Output is correct |
| 44 |
Correct |
53 ms |
2156 KB |
Output is correct |
| 45 |
Correct |
53 ms |
2156 KB |
Output is correct |
| 46 |
Correct |
56 ms |
2156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2024 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
2028 KB |
Execution killed because of forbidden syscall gettid (186) |
| 3 |
Halted |
0 ms |
0 KB |
- |
