mickypinata

TUMSO18: EZ Problem

Jul 22nd, 2021
936
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int logN = log2(1e18);
  7. const int MD = 1e9 + 7;
  8.  
  9. int blift[logN + 1];
  10.  
  11. int modExp(int base, lli exp){
  12.     blift[0] = base % MD;
  13.     for(int e = 1; e <= logN; ++e){
  14.         blift[e] = ((lli)blift[e - 1] * blift[e - 1]) % MD;
  15.     }
  16.     int ans = 1;
  17.     for(int e = logN; e >= 0; --e){
  18.         if(exp >= ((lli)1 << e)){
  19.             ans = ((lli)ans * blift[e]) % MD;
  20.             exp -= ((lli)1 << e);
  21.         }
  22.     }
  23.     return ans;
  24. }
  25.  
  26. int main(){
  27.  
  28.     int Q;
  29.     scanf("%d", &Q);
  30.     while(Q--){
  31.         lli n;
  32.         int a;
  33.         scanf("%lld%d", &n, &a);
  34.         if(n == 0){
  35.             cout << "0\n";
  36.             continue;
  37.         }
  38.         int part1 = modExp(a + a, n - 1);
  39.         int part2 = (MD + (lli)part1 * (a + a) - 1) % MD;
  40.         int part3 = modExp(a + a - 1, MD - 2);
  41.         cout << (((lli)part1 * part2) % MD * part3) % MD << '\n';
  42.     }
  43.  
  44.     return 0;
  45. }
  46.  
RAW Paste Data