結果
問題 |
No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."
|
ユーザー |
![]() |
提出日時 | 2025-06-11 15:02:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,165 bytes |
コンパイル時間 | 2,117 ms |
コンパイル使用メモリ | 227,832 KB |
実行使用メモリ | 50,912 KB |
最終ジャッジ日時 | 2025-06-11 23:07:15 |
合計ジャッジ時間 | 9,292 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 WA * 1 |
ソースコード
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; #define Loop(x,l,r) for (ll x = ll(l); x < ll(r); ++x) #define LoopR(x,l,r) for (ll x = ll(r)-1; x >= ll(l); --x) #define Looc(x,l,r) for (ll x = ll(l); x <= ll(r); ++x) #define LoocR(x,l,r) for (ll x = ll(r); x >= ll(l); --x) //#define int ll typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #ifndef DB #define DB 0 #define endl '\n' #endif #define debugl(l) if constexpr ((l) < DB) #define debug debugl(0) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template<class T> using better_map = __gnu_pbds::gp_hash_table<ll, T, custom_hash>; int mod; ll pw(ll x, ll y) { ll a = 1; while (y) { if (y%2) a = a*x % mod; x = x*x % mod; y /= 2; } return a; } ll inv(ll x) { return pw(x, mod-2); } struct Mat : array<ll, 4> { Mat operator*(const Mat &m) const { return { (at(0) * m[0] + at(1) * m[2]) % mod, (at(0) * m[1] + at(1) * m[3]) % mod, (at(2) * m[0] + at(3) * m[2]) % mod, (at(2) * m[1] + at(3) * m[3]) % mod, }; } Mat &operator*=(const Mat &m) { return *this = *this * m; } ll det() const { return ((at(0) * at(3) - at(1) * at(2))%mod+mod)%mod; } Mat inv() const { return Mat{ at(3), (mod - at(1)) % mod, (mod - at(2)) % mod, at(0), } * ::inv(det()); } pll up () const { return {at(0), at(1)}; } pll down() const { return {at(2), at(3)}; } Mat operator*(ll d) const { Mat ans = *this; for (auto &x : ans) x = x * d % mod; return ans; } }; pll operator*(const pll &v, const Mat &m) { Mat vm = { v.first, v.second, 0, 0, }; vm *= m; return {vm[0], vm[1]}; } const Mat I = {1, 0, 0, 1}; Mat A, B, Ap; better_map<ll> up; ll mypair(int x, int y) { return ((ll)x << 32) ^ y; } ll mypair(pll p) { return mypair((int)p.first, (int)p.second); } void solve_det0() { int p = 0; Mat m = I; while (p < mod + 10 && m != B) { m *= A; p++; } cout << (m == B? p: -1) << '\n'; } void make_updown() { up.clear(); Mat m = I; Loop (i,0,mod) { m *= A; up.insert({mypair(m.up()), i+1}); } Ap = m; } ll find(const better_map<ll> &small, pll target) { ll p = 0; Mat mi = I; Mat Api = Ap.inv(); Loop (_,0,mod) { // x * m = target // x = target * m.inv pll cand = target * mi; auto it = small.find(mypair(cand)); if (it != small.end()) { debugl(1) { cerr << "find//////\n"; cerr << cand.first << ' ' << cand.second << '\n'; cerr << "*\n"; auto m = mi.inv(); cerr << m[0] << ' ' << m[1] << '\n'; cerr << m[1] << ' ' << m[2] << '\n'; cerr << "=\n"; cerr << target.first << ' ' << target.second << '\n'; cerr << "//////////\n"; } return p + it->second; } mi *= Api; p += mod; } return -1; } Mat pw(Mat x, ll y) { Mat a = I; while (y) { if (y%2) a *= x; x *= x; y /= 2; } return a; } void solve() { cin >> mod; Loop (i,0,4) cin >> A[i]; Loop (i,0,4) cin >> B[i]; if (A == B) { cout << "1\n"; return; } if (B == I) { cout << "0\n"; return; } if (A == Mat{}) { cout << "-1\n"; return; } if (!A.det()) { return solve_det0(); } make_updown(); ll l1 = find(up , {1, 0}); ll p1 = find(up , B.up ()); debug { cerr << "a % " << l1 << " = " << p1 << '\n'; //cerr << "a % " << l2 << " = " << p2 << '\n'; } if (p1 == -1) { cout << "-1\n"; return; } ll ans = p1 % l1; auto m = pw(A, ans); if (m != B) { cout << "-1\n"; return; } debug { cerr << "debug///\n"; cerr << m[0] << ' ' << m[1] << '\n'; cerr << m[2] << ' ' << m[3] << '\n'; if (m != B) cerr << "ERROR!!!!!!!!!!!!!!!!!!!\n"; cerr << "////////\n"; } cout << ans << '\n'; } signed main() { cin.tie(0) -> sync_with_stdio(false); int t = 1; cin >> t; while (t--) solve(); }