algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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 }