#include "gondola.h" #include <bits/stdc++.h> using namespace std; #define ll long long const ll mod = 1e9+9; ll po(ll n, ll k) { if (k == 0) return 1; else if (k & 1) return n * po((n * n) % mod, k / 2) % mod; return po((n * n) % mod, k / 2); } int valid(int n, int sequence[]) { vector<int> a(sequence, sequence + n); set<int> s; for (int i = 0; i < n; i++) { a[i]--; s.insert(a[i]); } if (s.size() != n) return 0; int j = 0; bool ok = 1; for (int i = 0; i < n; i++) { if (a[i] < n) { ok = 0; j = (i - a[i] + n) % n; break; } } if (ok) return 1; for (int k = 0; k < n; k++, j++) { if (a[j % n] < n && a[j % n] != k) { return 0; } } return 1; } //---------------------- int replacement(int n, int sequence[], int ans[]) { vector<int> a(sequence, sequence + n); int j = -1; for (int i = 0; i < n; i++) if (a[i] <= n) { j = (i - (a[i] - 1) + n) % n; break; } if (j == -1) j = 1; vector<int> initial(n); for (int i = 0; i < n; i++) initial[i] = (i - j + n) % n + 1; set<pair<int, int>> change; for (int i = 0; i < n; i++) { if (a[i] > n) change.insert({a[i], i}); } int index = 0; int now = n; for (auto it = change.begin(); it != change.end(); ++it) { int value = it->first; int idx = it->second; ans[index++] = initial[idx]; for (int x = now + 1; x < value; x++) ans[index++] = x; now = value; } return index; } //---------------------- int countReplacement(int n, int inputSeq[]) { if (!valid(n, inputSeq)) return 0; vector<int> a(inputSeq, inputSeq + n); vector<int> change; int intangible = 0; for (int i = 0; i < n; i++) { if (a[i] <= n) intangible++; else change.push_back(a[i]); } if (change.empty()) return 1; sort(change.begin(), change.end()); int ans = 1; if (intangible == 0) ans = (1ll * ans * n) % mod; int now = n; int remaining = change.size(); for (int value : change) { int dist = value - now - 1; if (dist > 0) ans = (1ll * ans * po(remaining, dist)) % mod; now = value; remaining--; } return ans; }