fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define REP(i, a, b) for (int i = (a); i <= (b); ++i)
  5. #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
  6. #define FORD(i, a, b) for(int i = (a); i > (b); --i)
  7. #define REPD(i, a, b) for(int i = (a); i >=(b); --i)
  8. #define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  9. #define endl '\n'
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pf push_front
  13. #define popb pop_back
  14. #define popf pop_front
  15. #define ins insert
  16. #define all(x) (x).begin(),(x).end()
  17. #define rall(x) (x).rbegin(),(x).rend()
  18. #define unmap unordered_map
  19. #define pq priority_queue
  20. #define minEle min_element
  21. #define maxEle max_element
  22. #define lb lower_bound //first pos >= val
  23. #define ub upper_bound // first pos > val
  24. #define bp __builtin_popcount
  25. #define debug(a) cout << a << endl
  26. using namespace std;
  27.  
  28. typedef long long ll;
  29. typedef long double ld;
  30. typedef pair <ll, ll> pll;
  31. typedef pair <int, int> pii;
  32. typedef pair <pii, int> ppi;
  33. typedef pair <int, pii> pip;
  34. typedef pair <ll, ld> pld;
  35. typedef pair <ll, pll> pllp;
  36. typedef pair <pll, ll> ppll;
  37. typedef vector <int> vi;
  38. typedef vector <ll> vll;
  39. typedef vector <pll> vpll;
  40. typedef vector <pii> vpii;
  41. typedef map <int, int> mii;
  42. typedef map <ll, ll> mll;
  43. typedef string BigNum;
  44.  
  45. const ll maxN = 1e18;
  46. const ll minN = -1e18;
  47. const int INF = 2e9;
  48. const ll MOD = 1e9 + 7;
  49. const ll MOD1 = 998244353;
  50. const int baseHash = 331;
  51. const int bigNumLength = 5000;
  52. const ld PI = acos(-1);
  53.  
  54. //Remember limit for IT, etc..., and +1 in limit of any array
  55. const ll limit = 2e5 + 5;
  56. const ll limit1 = 1e6 + 5;
  57. const ll limit2 = 1e3 + 5;
  58. //If TLE let's use int instead of ll because it's as slow as your WPM :)))
  59.  
  60. /*----IMPORTANT THINGS----*/
  61. pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
  62. //right down left up rightdown leftdown rightup leftup
  63. pii NON = {-1, -1};
  64. /*------------------------*/
  65.  
  66. int t, a2, n, mod;
  67.  
  68. struct Matrix {
  69.     vector <vi> c;
  70.     int rows, cols;
  71.  
  72.     Matrix(int rows, int cols) : rows(rows), cols(cols) {
  73.         c.resize(rows);
  74.         FOR(i, 0, rows) c[i].resize(cols);
  75.     }
  76.  
  77.     Matrix operator * (const Matrix &other) {
  78.         Matrix ans(rows, other.cols);
  79.  
  80.         FOR(i, 0, rows) {
  81.             FOR(j, 0, other.cols) {
  82.                 ans.c[i][j] = 0;
  83.  
  84.                 FOR(k, 0, cols) {
  85.                     ans.c[i][j] += (1LL * c[i][k] * other.c[k][j]) % mod;
  86.                     ans.c[i][j] %= mod;
  87.                 }
  88.             }
  89.         }
  90.  
  91.         return ans;
  92.     }
  93.  
  94.     Matrix power(const ll &n) {
  95.         if (n == 1) return (*this);
  96.  
  97.         Matrix ans = power(n >> 1);
  98.         return (n & 1) ? ans * ans * (*this) : ans * ans;
  99.     }
  100. };
  101.  
  102. void solveProblem() {
  103.     Matrix ans(4, 4);
  104.  
  105.     ans.c[0][0] = 1, ans.c[0][1] = 0, ans.c[0][2] = 0, ans.c[0][3] = 0;
  106.     ans.c[1][0] = (4LL * a2 * a2) % mod, ans.c[1][1] = (4LL * a2 * a2) % mod, ans.c[1][2] = 1, ans.c[1][3] = 2LL * a2 % mod;
  107.     ans.c[2][0] = 1, ans.c[2][1] = 1, ans.c[2][2] = 0, ans.c[2][3] = 0;
  108.     ans.c[3][0] = (mod + (-4LL * a2 % mod)); ans.c[3][1] = (mod + (-4LL * a2 % mod)); ans.c[3][2] = 0, ans.c[3][3] = mod - 1;
  109.  
  110.     if (n <= 2) {
  111.         cout << (n == 1 ? 1 % mod : (1LL + 1LL * a2 * a2) % mod) << endl;
  112.         return;
  113.     }
  114.  
  115.     ans = ans.power(n - 2);
  116.     int res = 0;
  117.     int sum12 = (1LL + 1LL * a2 * a2) % mod;
  118.  
  119.     (res += (1LL * sum12 * ans.c[0][0]) % mod) %= mod;
  120.     (res += 1LL * ans.c[1][0] * a2 % mod * a2 % mod) %= mod;
  121.     (res += 1LL * ans.c[2][0]) %= mod;
  122.     (res += 1LL * ans.c[3][0] * a2 % mod) %= mod;
  123.  
  124.     cout << (res + mod) % mod << endl;
  125. }
  126.  
  127. void fastInput() {
  128.     ios_base::sync_with_stdio(0);
  129.     cin.tie(0);
  130.     cout.tie(0);
  131. }
  132.  
  133. void readInput() {
  134.     cin >> t;
  135.     while (t--) {
  136.         cin >> a2 >> n >> mod;
  137.  
  138.         solveProblem();
  139.     }
  140. }
  141.  
  142. int main() {
  143.     fastInput();
  144.     readInput();
  145. //    solveProblem();
  146. }
  147.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hOVQdJ
language:
C++14 (gcc 8.3)
created:
179 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!