#include "gondola.h" #include <bits//stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #define ll long long #define ld long double #define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1)) #define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1)) #define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1)) #define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1)) #define iloop_(m, h, g) for (auto i = m; i < h; i += g) #define jloop_(m, h, g) for (auto j = m; j < h; j += g) #define kloop_(m, h, g) for (auto k = m; k < h; k += g) #define lloop_(m, h, g) for (auto l = m; l < h; l += g) #define getchar_unlocked _getchar_nolock // comment before submission #define pll pair<ll, ll> #define plll pair<ll, pll> #define pllll pair<pll, pll> #define vll vector<ll> #define qll queue<ll> #define dll deque<ll> #define pqll priority_queue<ll> #define gll greater<ll> #define INF 1000000000000000 #define MOD1 1000000007 #define MOD2 998244353 #define MOD3 1000000009 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int valid(int n, int inputSeq[]) { ll cv = -1; set<ll> st; iloop(0, n) { st.insert(inputSeq[i]); if (inputSeq[i] <= n) { if (cv != -1 && (inputSeq[i] - i + n)%n != cv) return 0; cv = (inputSeq[i] - i + n)%n; } } return (ll)st.size() == n; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { vector<pll> tof; ll cv = -1; iloop(0, n) { if (gondolaSeq[i] <= n) cv = (gondolaSeq[i] - i + n)%n; else tof.push_back({gondolaSeq[i], i}); } if (cv == -1) cv = 0; if (tof.size()) sort(tof.begin(), tof.end()); ll ccn = 0, un = n+1; for (auto it : tof) { ll og = (it.second + cv)%n; if (og == 0) og = n; replacementSeq[ccn] = og; ccn++; while (un < it.first) { replacementSeq[ccn] = un; ccn++; un++; } un++; } return ccn; } //---------------------- ll exp(ll a, ll b) { if (b == 0) return 1; if (b == 1) return a%MOD3; ll res = exp(a, b/2); if (b%2 == 0) return (res*res)%MOD3; return (((res*res)%MOD3)*(a%MOD3))%MOD3; } int countReplacement(int n, int inputSeq[]) { if (!valid(n, inputSeq)) return 0; if (*max_element(inputSeq, inputSeq + n) == n) return 1; vector<ll> req; iloop(0, n) if (inputSeq[i] > n) req.push_back(inputSeq[i]); sort(req.begin(), req.end()); ll cans = 1; ll cv = n+1, cav = req.size(); for (auto it : req) { cans *= exp(cav, (ll)it - cv); cans %= MOD3; cav--; cv = it + 1; } if ((ll)req.size() == n) {cans *= n; cans %= MOD3;} return cans; }