| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1080561 | eyalz | 마술쇼 (APIO24_show) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}