結果
問題 |
No.2748 Strange Clock
|
ユーザー |
👑 ![]() |
提出日時 | 2024-04-21 15:30:32 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,785 ms / 2,000 ms |
コード長 | 1,692 bytes |
コンパイル時間 | 3,214 ms |
コンパイル使用メモリ | 124,160 KB |
最終ジャッジ日時 | 2025-02-21 08:14:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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(); rep(i,1<<30) if(i%3 == 0){ i64 t = i; vector<i64> dig; rep(n,N){ dig.push_back(t%3); t /= 3; } if(t) break; reverse(dig.begin(), dig.end()); i64 t3 = 0; for(i64 a : dig) t3 = t3 * 3 + a; i64 t4 = 0; for(i64 a : dig) t4 = t4 * 4 + a; i64 t6 = 0; for(i64 a : dig) t6 = t6 * 6 + a; 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; }