#include "gondola.h" #include <bits/stdc++.h> using namespace std; const long long mod = 1000000009LL; int valid(int n, int a[]){ // không sửa a[], kiểm tra theo vòng (circular) unordered_set<int> seen; int st = -1; for (int i = 0; i < n; ++i){ if (seen.count(a[i])) return 0; seen.insert(a[i]); if (a[i] <= n && st == -1) st = i; } if (st == -1) return 1; // tất cả là spare -> hợp lệ int prev = a[st]; for (int j = 1; j < n; ++j){ int idx = (st + j) % n; int expected = (prev % n) + 1; if (a[idx] <= n){ if (a[idx] != expected) return 0; prev = a[idx]; } else { // spare: nó tương ứng với giá trị expected (tăng chuỗi) prev = expected; } } return 1; } int replacement(int n, int a[], int replacementSeq[]){ // tạo bản sao b[] để không sửa a[] vector<int> b(n); for (int i = 0; i < n; ++i) b[i] = a[i]; int st = -1; for (int i = 0; i < n; ++i) if (b[i] <= n && st == -1) st = i; vector<pair<int,int>> v; // (startExpected, spareLabel) if (st == -1){ // không có gondola gốc: giả sử bắt đầu bằng 1 tại vị trí 0 st = 0; v.push_back({1, b[0]}); b[0] = 1; } int prev = b[st]; for (int j = 1; j < n; ++j){ int idx = (st + j) % n; int expected = (prev % n) + 1; if (b[idx] > n){ v.push_back({expected, b[idx]}); b[idx] = expected; // lấp chỗ bằng expected để tiếp tục mô phỏng prev = b[idx]; } else { prev = b[idx]; } } sort(v.begin(), v.end(), [](const pair<int,int>& x, const pair<int,int>& y){ return x.second < y.second; }); int opt = 0; int cur = n; for (auto &p : v){ int first = p.first; // số gondola gốc (1..n) đi hỏng ngay lúc đó int second = p.second; // nhãn spare xuất hiện ở vị trí đó (> n) // luôn đưa số đầu (gondola gốc) vào replacement sequence replacementSeq[opt++] = first; // sau đó các spare numbers (n+1 ... second-1) bị tạo trước khi spare 'second' for (int s = cur + 1; s < second; ++s){ replacementSeq[opt++] = s; } if (second - 1 > cur) cur = second - 1; } return opt; } long long binpow(long long base, long long e){ long long res = 1; while (e > 0){ if (e & 1) res = (res * base) % mod; base = (base * base) % mod; e >>= 1; } return res; } int countReplacement(int n, int a[]){ // không thay đổi a[] ở đây int st = -1; for (int i = 0; i < n; ++i) if (a[i] <= n && st == -1) st = i; vector<int> v; for (int i = 0; i < n; ++i) if (a[i] > n) v.push_back(a[i]); if (!valid(n, a)) return 0; sort(v.begin(), v.end()); long long res = 1; int cur = n; int cnt = (int)v.size(); for (int x : v){ long long exp = (long long)(x - 1 - cur); if (exp > 0){ res = (res * binpow(cnt, exp)) % mod; } cur = x; cnt--; } if (st == -1) res = (res * (long long)n) % mod; return (int)res; }