結果
問題 |
No.2748 Strange Clock
|
ユーザー |
👑 ![]() |
提出日時 | 2024-04-21 15:38:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 906 ms / 2,000 ms |
コード長 | 1,856 bytes |
コンパイル時間 | 1,063 ms |
コンパイル使用メモリ | 84,904 KB |
最終ジャッジ日時 | 2025-02-21 08:14:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <atcoder/modint> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<int(n); i++) #define repr(i,n) for(int i=int(n)-1; i>=0; i--) using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 N, M; cin >> N >> M; vector<pair<i64,i64>> T; i64 cycleTime = 1; rep(i,N) cycleTime *= 12; i64 cycleTime3 = 1; rep(i,N) cycleTime3 *= 3; i64 cycleTime4 = 1; rep(i,N) cycleTime4 *= 4; i64 cycleTime6 = 1; rep(i,N) cycleTime6 *= 6; using Modint = atcoder::modint; Modint::set_mod(cycleTime3); i64 MxInv = Modint(cycleTime4).inv().val(); { vector<i64> t3u(16), t4u(16), t6u(16); t4u[1] = 4; t4u[2] = 4; for(int i=3; i<N; i++) t4u[i] = t4u[i-1] * 4; t6u[1] = 6; t6u[2] = 18; for(int i=3; i<N; i++) t6u[i] = t6u[i-1] * 6; i64 t4 = 0; i64 t6 = 0; for(i64 t3=0; t3<cycleTime3; t3+=3){ if(t3){ i64 t = t3; for(int i=1; t%3 == 0; i++){ t4 += t4u[i]; t6 += t6u[i]; t /= 3; } } i64 t12 = (t4 + (i64(Modint(MxInv * (t3 - t4)).val()) << (N*2))); i64 sl = (t12 + cycleTime6 - t6) % cycleTime6; T.push_back({ sl, t12 }); } } sort(T.begin(), T.end()); i64 ans = 0; for(i64 l=0; l<i64(T.size()); ){ i64 r = l+1; while(r < i64(T.size()) && T[l].first == T[r].first) r++; auto t = vector<i64>(r-l+1); for(i64 i=l; i<r; i++) t[i-l] = T[i].second; t[r-l] = t[0] + cycleTime; rep(i,r-l) if(t[i+1] - t[i] >= M+3) ans += 1; l = r; } cout << ans << endl; return 0; }