제출 #1080561

#제출 시각아이디문제언어결과실행 시간메모리
1080561eyalz마술쇼 (APIO24_show)C++17
컴파일 에러
0 ms0 KiB
#include"Alice.h" #include<bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using llong = long long; using pii = pair<int,int>; using vpii = vector<pii>; using vb = vector<bool>; constexpr int N = 45; constexpr int p = 23; int C[N],V[d][d],Y[d]; vpii Alice() { llong X = setN(N) - 1; // turn to rep in base factorial: d digits for(int i = 1; i <= d; ++i) { C[i] = Y[i-1] = X % i; X /= i; } // find polynomial for(int i = 0; i < d; ++i) { int a = 1; for(int j = 0; j < d; ++j) { V[i][j] = a; a = a * i % p; } } for(int i = 0; i < d; ++i) { int e = 1; int a = V[i][i]; for(int w = p-2; w; w>>=1) { if(w&1) e = e * a % p; a = a * a % p; } for(int k = i; k < d; ++k) V[i][k] = e * V[i][k] % p; Y[i] = e * Y[i] % p; for(int j = 0; j < d; ++j)if(i != j) { int ej = (p - V[j][i]) % p; for(int k = 0; k < d; ++k) V[j][k] = (V[j][k] + ej * V[i][k] % p) % p; Y[j] = (Y[j] + ej * Y[i] % p) % p; } } // evaluate the derivative at d points for(int i = 0; i < d; ++i) { int r = 0; int a = 1; for(int j = 1; j < d; ++j) { r = (r + a * Y[j] % p * j % p) % p; a = a * i % p; } C[i+d+1] = r; } // encode to tree vpii T; T.reserve(N-1); for(int i = 1; i < N; ++i) T.push_back({i+1, C[i]+1}); return T; }
#include"Bob.h" #include<bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using llong = long long; using pii = pair<int,int>; using vpii = vector<pii>; using vb = vector<bool>; constexpr int N = 45; constexpr int p = 23; constexpr int d = p-1; int V[d][d], Y[d], P[d]; llong Bob(vpii T) { // sort such that the matrix rows are correctly ordered for(int i = 0; i < T.size(); ++i) if(T[i].first < T[i].second) T[i] = {T[i].second, T[i].first}; sort(T.begin(), T.end()); // decode tree for(int c = 0; auto[a,b]:T) { if(c >= d) break; if(a < b) swap(a,b); --a; --b; // polynomial value if(a <= d) { a -= 1; int f = 1; for(int i = 0; i < d; ++i) { V[c][i] = f; f = f * a % p; } } // derivative value else { a -= d+1; int f = 1; V[c][0] = 0; for(int i = 1; i < d; ++i) { V[c][i] = f * i % p; f = f * a % p; } } Y[c] = b; ++c; } // interpolate for(int i = 0; i < d; ++i) { int e = 1; int a = V[i][i]; // need row swap if(a == 0) { // find first good row int c = i+1; while(V[c][i] == 0) ++c; // swap for(int j = 0; j < d; ++j) swap(V[i][j], V[c][j]); swap(Y[i], Y[c]); a = V[i][i]; } // calculate inverse for(int w = p-2; w; w >>= 1) { if(w&1) e = e * a % p; a = a * a % p; } // make leftmost value in row be 1 for(int k = i; k < d; ++k) V[i][k] = e * V[i][k] % p; Y[i] = e * Y[i] % p; //reduce all values in column to 0 for(int j = 0; j < d; ++j)if(i != j) { int ej = (p - V[j][i]) % p; for(int k = 0; k < d; ++k) V[j][k] = (V[j][k] + ej * V[i][k] % p) % p; Y[j] = (Y[j] + ej * Y[i] % p) % p; } } // find the original d values for(int i = 0; i < d; ++i) { int r = 0; int a = 1; for(int j = 0; j < d; ++j) { r = (r + a * Y[j] % p) % p; a = a * i % p; } P[i] = r; } // convert to X llong X = 0; llong a = 1; for(int i = 0; i < d; ++i) { X += a * P[i]; a *= (i+1); } return X+1; }

컴파일 시 표준 에러 (stderr) 메시지

Alice.cpp:14:12: error: 'd' was not declared in this scope
   14 | int C[N],V[d][d],Y[d];
      |            ^
Alice.cpp:14:15: error: 'd' was not declared in this scope
   14 | int C[N],V[d][d],Y[d];
      |               ^
Alice.cpp:14:20: error: 'd' was not declared in this scope
   14 | int C[N],V[d][d],Y[d];
      |                    ^
Alice.cpp: In function 'vpii Alice()':
Alice.cpp:19:25: error: 'd' was not declared in this scope
   19 |     for(int i = 1; i <= d; ++i)
      |                         ^
Alice.cpp:21:16: error: 'Y' was not declared in this scope
   21 |         C[i] = Y[i-1] = X % i;
      |                ^
Alice.cpp:25:24: error: 'd' was not declared in this scope
   25 |     for(int i = 0; i < d; ++i)
      |                        ^
Alice.cpp:30:13: error: 'V' was not declared in this scope
   30 |             V[i][j] = a;
      |             ^
Alice.cpp:34:24: error: 'd' was not declared in this scope
   34 |     for(int i = 0; i < d; ++i)
      |                        ^
Alice.cpp:37:17: error: 'V' was not declared in this scope
   37 |         int a = V[i][i];
      |                 ^
Alice.cpp:45:9: error: 'Y' was not declared in this scope
   45 |         Y[i] = e * Y[i] % p;
      |         ^
Alice.cpp:55:24: error: 'd' was not declared in this scope
   55 |     for(int i = 0; i < d; ++i)
      |                        ^
Alice.cpp:61:26: error: 'Y' was not declared in this scope
   61 |             r = (r + a * Y[j] % p * j % p) % p;
      |                          ^

Bob.cpp: In function 'llong Bob(vpii)':
Bob.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < T.size(); ++i) if(T[i].first < T[i].second) T[i] = {T[i].second, T[i].first};
      |                    ~~^~~~~~~~~~
Bob.cpp:22:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   22 |     for(int c = 0; auto[a,b]:T)
      |                    ^~~~