#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/ioi14_d2/debug.h"
#else
#define debug(...) void(37)
#endif
template<typename T>
vector<T> inverse_fuck(T* a, int N) {
vector<T> res(N);
for (int i = 0; i < N; ++i) {
res[i] = a[i];
}
return res;
}
constexpr int md = 1,000,000,009;
struct Mint {
int val = 0;
Mint() : val(0) { }
template<typename T>
Mint(T x) {
if (-md <= x && x < md) {
val = x;
} else {
val = x % md;
}
if (val < 0) {
val += md;
}
}
int& operator()() { return val; }
Mint& operator+=(Mint x) {
if ((val += x.val) > md) {
val -= md;
}
return *this;
}
Mint& operator-=(Mint x) {
if ((val -= x.val) < 0) {
val += md;
}
return *this;
}
Mint& operator*=(Mint x) {
val = int(1LL * val * x.val % md);
return *this;
}
};
Mint operator+(Mint x, Mint y) {
return x += y;
}
Mint operator-(Mint x, Mint y) {
return x -= y;
}
Mint operator*(Mint x, Mint y) {
return x *= y;
}
string to_string(Mint x) {
return to_string(x.val);
}
template<typename T>
Mint power(Mint x, T p) {
Mint res = 1;
while (p > 0) {
if (p & 1) {
res *= x;
}
x *= x;
p >>= 1;
}
return res;
}
int valid(int N, int inputSeq[])
{
auto A = inverse_fuck(inputSeq, N);
int prev = -1;
for (int i = 0; i < N; ++i) {
if (A[i] <= N) {
if (prev != -1) {
if (i - prev != (A[i] - A[prev] + N) % N) {
return false;
}
}
prev = i;
}
}
return set<int>(A.begin(), A.end()).size() == A.size();
}
//----------------------
int replacement(int N, int inputSeq[], int replacementSeq[])
{
auto A = inverse_fuck(inputSeq, N);
int mn = min_element(A.begin(), A.end()) - A.begin();
vector<int> cur(N);
for (int i = 0; i < N; ++i) {
cur[(mn + i) % N] = (A[mn] + i - 1) % N + 1;
}
debug(A, cur);
int mx = max_element(A.begin(), A.end()) - A.begin();
vector<int> pos(A[mx] + 1, -1);
for (int i = 0; i < N; ++i) {
pos[A[i]] = i;
}
debug(pos);
vector<int> ans;
for (int i = N + 1; i <= A[mx]; ++i) {
int use = (pos[i] == -1 ? mx : pos[i]);
ans.push_back(cur[use]);
cur[use] = i;
}
for (int i = 0; i < int(ans.size()); ++i) {
replacementSeq[i] = ans[i];
}
return int(ans.size());
}
//----------------------
int countReplacement(int N, int inputSeq[])
{
auto A = inverse_fuck(inputSeq, N);
if (!valid(N, inputSeq)) {
return 0;
}
sort(A.begin(), A.end());
Mint res = 1;
int prev = N;
for (int i = 0; i < N; ++i) {
if (A[i] <= N) {
continue;
}
res *= power(N - i, A[i] - prev - 1);
prev = A[i];
}
return res();
}
Compilation message
gondola.cpp:21:30: error: invalid digit "9" in octal constant
21 | constexpr int md = 1,000,000,009;
| ^~~
gondola.cpp:21:22: error: expected unqualified-id before numeric constant
21 | constexpr int md = 1,000,000,009;
| ^~~
