Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("O3", "unroll-loops")
- #include <iostream>
- #include <iomanip>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- #include <string>
- #include <map>
- #include <unordered_map>
- #include <set>
- #include <unordered_set>
- #include <bitset>
- #include <sstream>
- #include <deque>
- #include <queue>
- #include <complex>
- #include <random>
- #include <cassert>
- #include <chrono>
- using namespace std;
- #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
- #define FIXED cout << fixed << setprecision(12)
- #define ll long long
- #define ld long double
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define graph vector<vector<int>>
- #define pb push_back
- #define pf push_front
- #define popb pop_back
- #define popf pop_front
- #define f first
- #define s second
- #define hashmap unordered_map
- #define hashset unordered_set
- #define eps 1e-9
- #define mod 1000000007
- #define inf 3000000000000000007ll
- #define sz(a) signed(a.size())
- #define all(a) a.begin(), a.end()
- #define rall(a) a.rbegin(), a.rend()
- #ifdef DEBUG
- mt19937 gen(857204);
- #else
- mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
- #endif
- template<class T, class U> inline void checkmin(T &x, U y) { if (y < x) x = y; }
- template<class T, class U> inline void checkmax(T &x, U y) { if (y > x) x = y; }
- template<class T, class U> inline bool ifmax(T &x, U y) { if (y > x) return x = y, true; return false; }
- template<class T, class U> inline bool ifmin(T &x, U y) { if (y < x) return x = y, true; return false; }
- template<class T> inline void sort(T &a) { sort(all(a)); }
- template<class T> inline void rsort(T &a) { sort(rall(a)); }
- template<class T> inline void reverse(T &a) { reverse(all(a)); }
- template<class T, class U> inline istream& operator>>(istream& str, pair<T, U> &p) { return str >> p.f >> p.s; }
- template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }
- template<class T> inline T sorted(T a) { sort(a); return a; }
- struct zet {
- int val;
- explicit operator int() const { return val; }
- zet(ll x = 0) { val = (x >= -mod && x < mod ? x : x % mod); if (val < 0) val += mod; }
- zet(ll a, ll b) { *this += a; *this /= b; }
- zet& operator+=(zet const &b) { val += b.val; if (val >= mod) val -= mod; return *this; }
- zet& operator-=(zet const &b) { val -= b.val; if (val < 0) val += mod; return *this; }
- zet& operator*=(zet const &b) { val = (val * (ll)b.val) % mod; return *this; }
- friend zet mypow(zet a, ll n) {
- zet res = 1;
- while (n) { if (n & 1) res *= a; a *= a; n >>= 1; }
- return res;
- }
- friend zet inv(zet a) { return mypow(a, mod - 2); }
- zet& operator/=(zet const& b) { return *this *= inv(b); }
- friend zet operator+(zet a, const zet &b) { return a += b; }
- friend zet operator-(zet a, const zet &b) { return a -= b; }
- friend zet operator-(zet a) { return 0 - a; }
- friend zet operator*(zet a, const zet &b) { return a *= b; }
- friend zet operator/(zet a, const zet &b) { return a /= b; }
- friend istream& operator>>(istream& stream, zet &a) { return stream >> a.val; }
- friend ostream& operator<<(ostream& stream, const zet &a) { return stream << a.val; }
- friend bool operator==(zet const &a, zet const &b) { return a.val == b.val; }
- friend bool operator!=(zet const &a, zet const &b) { return a.val != b.val; }
- friend bool operator<(zet const &a, zet const &b) { return a.val < b.val; }
- };
- vector<vector<zet>> operator*(vector<vector<zet>> a, vector<vector<zet>> b) {
- assert(sz(a[0]) == sz(b));
- vector<vector<zet>> ans(sz(a), vector<zet>(sz(b[0])));
- for (int i = 0; i < sz(a); ++i)
- for (int j = 0; j < sz(b[0]); ++j)
- for (int r = 0; r < sz(a[0]); ++r)
- ans[i][j] += a[i][r] * b[r][j];
- return ans;
- }
- vector<vector<zet>> mpow(vector<vector<zet>> a, ll n) {
- assert(sz(a) == sz(a[0]));
- vector<vector<zet>> ans(sz(a), vector<zet>(sz(a[0])));
- for (int i = 0; i < sz(a); ++i) ans[i][i] = 1;
- while (n > 0) {
- if (n & 1) ans = ans * a;
- a = a * a;
- n >>= 1;
- }
- return ans;
- }
- signed main() {
- FAST; FIXED;
- ll n;
- cin >> n;
- if (n == 1) {
- cout << 1;
- return 0;
- }
- vector<vector<zet>> start = {
- {0, 0, 1},
- {0, 0, 0},
- {0, 0, 0}
- };
- for (int a = 0; a <= 10; ++a)
- for (int b = 0; b <= 10; ++b)
- for (int c = 0; c <= 10; ++c) {
- vector<vector<zet>> mul = {
- {0, 0, a},
- {1, 0, b},
- {0, 1, c}
- };
- start = start * mpow(mul, n - 1);
- for (int d = 0; d <= 10; ++d)
- for (int t = 0; t <= 10; ++t)
- for (int k = 0; k <= 10; ++k) {
- zet ans = 0;
- vector<zet> add = {0, d, t, k};
- for (int cnt = 1; cnt <= 3; ++cnt)
- ans += start[0][3 - cnt] * add[cnt];
- if (ans == 729888649) {
- cout << a << ' ' << b << ' ' << c << '\n';
- return 0;
- }
- }
- }
- #ifdef DEBUG
- cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement