Untitled
unknown
c_cpp
a year ago
2.2 kB
5
Indexable
#include <bits/stdc++.h> #define ll long long #define stp(n) fixed<<setprecision(n) #define flash cin.tie(0); cin.sync_with_stdio(0); #define el '\n' # define pll pair<ll,ll> # define pi pair<int,int> #define popCnt(x) (__builtin_popcountll(x)) #define LSB(x) (__builtin_ffsll(x) - 1) #define MSB(x) (64 - __builtin_clzll(x) - 1). using namespace std; //#pragma GCC optimize("03") //#pragma GCC target("tune=native") //#pragma GCC optimize("unroll-loops") const ll mod = 1e9 + 7; ll mul(const ll &a, const ll &b) { return (a % mod + mod) * (b % mod + mod) % mod; } ll add(const ll &a, const ll &b) { return (a + b + 2 * mod) % mod; } const int N = 5e3 + 9, inf = 2e9; const ll infl = 2e18; typedef vector<vector<double>> Matrix; Matrix operator*(Matrix matrix1, Matrix matrix2) { int m1 = matrix1.size(); int n1 = matrix1[0].size(); int n2 = matrix2[0].size(); Matrix result(m1, vector<double>(n2, 0)); for (int i = 0; i < m1; ++i) { for (int j = 0; j < n2; ++j) { for (int k = 0; k < n1; ++k) { result[i][j] += matrix1[i][k] * matrix2[k][j]; // result[i][j] %= mod; } } } return result; } Matrix binPow(Matrix a, long long b) { int n = a.size(); Matrix res(n, vector<double>(n, 0)); for (int i = 0; i < n; ++i) { res[i][i] = 1; } while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; } const double den = (1.0 + ::sqrt(2.0)); void testCase() { int n; double r; cin >> r >> n; n = min(n, 50); double c1 = r * den, r1 = r; Matrix init = {{c1, r1}, {0, 0}}; Matrix transition = {{1.0, 1.0 / den}, {-2, -2.0 / den}}; Matrix overallMalt = init * binPow(transition, n); cout << stp(7) << overallMalt[0][1] << el; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); flash; int T = 1; cin >> T; while (T--) { testCase(); // cout << el; // cout << endl; } }
Editor is loading...
Leave a Comment