main.cpp (2496B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 12 #define MV 1000000007LL 13 14 ll pw(ll base, ll exp) { 15 16 base %= MV; 17 long long result = 1; 18 19 while (exp > 0) { 20 if (exp & 1) { 21 result = result * base % MV; 22 } 23 24 base = base * base % MV; 25 exp = (exp >> 1); 26 } 27 return result; 28 } 29 30 int main() { 31 32 int testCases; 33 cin >> testCases; 34 35 // array a of length n 36 // one operation you may: 37 // replace the unique largest element in a with a strictly smaller positive value 38 // this can only be done when there's a unique max element of a 39 // find the number of unique arrays that can be made by performing the above 0 or more times 40 41 // output mod 10^9 + 7 42 43 // 3 44 // 2 2 1 45 46 // we can't perform any ops because 2 isn't unique 47 // 1 48 49 // 2 50 // 1000000000 1 51 // we can bring 1000000000 down to any value >= 1 or not change it so 52 // number of values = 1000000000 53 54 // 6 7 2 2 55 // we may bring 7 down to: 56 // 6 57 // 6622 (done) 58 // 5 59 // 6522 60 // 5522 61 // 4522 62 // 3522 63 // 2522 64 // 1522 65 // 4 66 // 6422 67 // 3 68 // 6322 69 // 2 70 // 6222 71 // 1 72 // 6122 73 74 // from a given state: 75 // bring max to same position as the value less than current 76 // max - max_2 77 // if we bring it to any value from (1 -> max_2-1) then 78 79 for(int z = 0; z < testCases; ++z) { 80 vector<long long> ls = {}; 81 int n = 0; 82 cin >> n; 83 84 for(int i = 0; i < n; ++i) { 85 int current = 0; 86 cin >> current; 87 ls.push_back(current); 88 } 89 90 sort(ls.begin(), ls.end()); 91 long long res = 1; 92 for (int k = 1; k <= n; ++k) { 93 long long current = ls[n - k]; 94 if (k >= 2 && ls[n - k + 1] == current) { 95 break; 96 } 97 if (k < n && ls[n - k - 1] == current) { 98 break; 99 } 100 res = (res + pw(current - 1, k)) % MV; 101 } 102 cout << res << "\n"; 103 104 } 105 }