fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace __gnu_pbds;
  4. #define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
  5. #define ll long long
  6. #define ld long double
  7. #define int long long
  8. #define endl "\n"
  9. #define yes cout<<"YES"<<endl;
  10. #define no cout<<"NO"<<endl;
  11. #define pb push_back
  12. #pragma GCC optimize("O3,unroll-loops")
  13. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  14. using namespace std;
  15. const int mod = 1e9+7;
  16. const int N = 1e5+5;
  17. const ll INF = 1e18;
  18. const ll MIN = -1e18;
  19. typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
  20.  
  21. inline int add(int a, int b) {
  22.     a += b;
  23.     return (a >= mod ? a - mod : a);
  24. }
  25.  
  26. inline int mult(int a, int b) {
  27.     return (a * b) % mod;
  28. }
  29.  
  30. constexpr int N_mat = 10;
  31.  
  32. struct Matrix {
  33.     int mat[N_mat][N_mat];
  34.     int len;
  35.  
  36.     Matrix(int n) : len(n) {
  37.         memset(mat, 0, sizeof(mat));
  38.     }
  39.  
  40.     Matrix operator*(const Matrix& other) const {
  41.         Matrix res(len);
  42.         for (int i = 1; i <= len; i++) {
  43.             for (int j = 1; j <= len; j++) {
  44.                 long long sum = 0;
  45.                 for (int k = 1; k <= len; k++) {
  46.                     sum += 1LL * mat[i][k] * other.mat[k][j];
  47.                 }
  48.                 res.mat[i][j] = sum % mod;
  49.             }
  50.         }
  51.         return res;
  52.     }
  53.  
  54.     Matrix operator+(const Matrix& other) const {
  55.         Matrix res(len);
  56.         for (int i = 1; i <= len; i++)
  57.             for (int j = 1; j <= len; j++)
  58.                 res.mat[i][j] = add(mat[i][j], other.mat[i][j]);
  59.         return res;
  60.     }
  61. };
  62.  
  63. Matrix expo_power(Matrix M, int K) {
  64.     Matrix res(M.len);
  65.     for (int i = 1; i <= M.len; i++) res.mat[i][i] = 1;
  66.     while (K) {
  67.         if (K & 1) res = res * M;
  68.         M = M * M;
  69.         K >>= 1;
  70.     }
  71.     return res;
  72. }
  73.  
  74. int inv(int a, int m) {
  75.     int m0 = m, x0 = 0, x1 = 1;
  76.     if (m == 1) return 0;
  77.     while (a > 1) {
  78.         int q = a / m;
  79.         tie(a, m) = make_pair(m, a % m);
  80.         tie(x1, x0) = make_pair(x0, x1 - q * x0);
  81.     }
  82.     return (x1 + m0) % m0;
  83. }
  84.  
  85. void resoudreSystemeModulaire(int a1, int b1, int c1, int a2, int b2, int c2) {
  86.     int D = ((a1 * b2 - a2 * b1) % mod + mod) % mod;
  87.     int Dx = ((c1 * b2 - c2 * b1) % mod + mod) % mod;
  88.     int Dy = ((a1 * c2 - a2 * c1) % mod + mod) % mod;
  89.     int invD = inv(D, mod);
  90.     int x = (Dx * invD) % mod;
  91.     int y = (Dy * invD) % mod;
  92.     cout << x << " " << y << endl;
  93. }
  94.  
  95. void solve() {
  96.     Matrix mt(2);
  97.     mt.mat[1][1] = mt.mat[1][2] = mt.mat[2][1] = 1;
  98.     int n, m, a, b;
  99.     cin >> n >> m >> a >> b;
  100.     int nb1a = 0, nb2a = 0, nb1b = 0, nb2b = 0;
  101.     if (n == 0) nb1a = 1;
  102.     else if (n == 1) nb2a = 1;
  103.     else {
  104.         auto res = expo_power(mt, n - 1);
  105.         nb2a = res.mat[1][1];
  106.         nb1a = res.mat[1][2];
  107.     }
  108.     if (m == 0) nb1b = 1;
  109.     else if (m == 1) nb2b = 1;
  110.     else {
  111.         auto res = expo_power(mt, m - 1);
  112.         nb2b = res.mat[1][1];
  113.         nb1b = res.mat[1][2];
  114.     }
  115.     resoudreSystemeModulaire(nb1a, nb2a, a, nb1b, nb2b, b);
  116. }
  117.  
  118. signed main() {
  119.     FAST;
  120.     auto begin = chrono::high_resolution_clock::now();
  121.     #ifndef ONLINE_JUDGE
  122.         freopen("input.txt", "r", stdin);
  123.         freopen("output.txt", "w", stdout);
  124.     #endif
  125.     int t = 1;
  126.     cin >> t;
  127.     while (t--) solve();
  128.     #ifndef ONLINE_JUDGE
  129.         auto end = chrono::high_resolution_clock::now();
  130.         cout << fixed << setprecision(4);
  131.         cout << "Execution time: " << chrono::duration_cast<chrono::duration<double>>(end - begin).count() << " seconds" << endl;
  132.     #endif
  133. }
  134.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
75907314 79511459
https://ideone.com/2EjOB7
language:
C++14 (clang 8.0)
created:
4 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!