結果
問題 | No.2748 Strange Clock |
ユーザー | 👑 Nachia |
提出日時 | 2024-04-20 20:11:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 694 ms / 2,000 ms |
コード長 | 5,581 bytes |
コンパイル時間 | 1,399 ms |
コンパイル使用メモリ | 98,656 KB |
実行使用メモリ | 36,320 KB |
最終ジャッジ日時 | 2024-04-20 20:11:36 |
合計ジャッジ時間 | 6,105 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 3 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 3 ms
5,376 KB |
testcase_16 | AC | 4 ms
5,376 KB |
testcase_17 | AC | 5 ms
5,376 KB |
testcase_18 | AC | 10 ms
5,376 KB |
testcase_19 | AC | 10 ms
5,376 KB |
testcase_20 | AC | 26 ms
5,376 KB |
testcase_21 | AC | 25 ms
5,376 KB |
testcase_22 | AC | 75 ms
7,520 KB |
testcase_23 | AC | 74 ms
7,520 KB |
testcase_24 | AC | 226 ms
19,680 KB |
testcase_25 | AC | 226 ms
19,808 KB |
testcase_26 | AC | 694 ms
36,320 KB |
testcase_27 | AC | 671 ms
36,104 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 230 ms
19,680 KB |
testcase_31 | AC | 253 ms
19,680 KB |
testcase_32 | AC | 225 ms
19,936 KB |
testcase_33 | AC | 673 ms
36,192 KB |
testcase_34 | AC | 2 ms
5,376 KB |
testcase_35 | AC | 2 ms
5,376 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> 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--) #include <cassert> namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair<long long, long long> ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ class DynamicModSupplier{ using u64 = unsigned long long; using Int = unsigned int; private: u64 imod; Int mod; // atcoder library u64 reduce2(u64 z) const noexcept { // atcoder library #ifdef _MSC_VER u64 x; _umul128(z, im, &x); #else using u128 = unsigned __int128; u64 x = (u64)(((u128)(z)*imod) >> 64); #endif return z - x * mod; } Int reduce(u64 z) const noexcept { Int v = reduce2(z); if(mod <= v) v += mod; return v; } public: DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) { assert(2 <= MOD); assert(MOD < (1u << 31)); imod = (u64)(-1) / mod + 1; } Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; } Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; } Int mul(Int a, Int b) const { return reduce((u64)a * b); } Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); } Int inv(Int a) const { Int v = ExtGcd(a, mod).first; return (v < mod) ? v : (v + mod); } Int pow(Int a, u64 i) const { Int r = a, ans = 1; while(i){ if(i & 1) ans = mul(ans, r); i /= 2; r = mul(r, r); } return ans; } Int getMod() const { return mod; } }; } // namespace nachia namespace nachia{ template<class FinishType> struct GarnerMod{ using Int = unsigned int; using IntLong = unsigned long long; std::vector<Int> mods; std::vector<DynamicModSupplier> dynmods; std::vector<std::vector<Int>> table_coeff; std::vector<Int> table_coeffinv; void precalc(std::vector<Int> new_mods){ mods = std::move(new_mods); dynmods.resize(mods.size()); for(size_t i=0; i<mods.size(); i++) dynmods[i] = DynamicModSupplier(mods[i]); int nmods = mods.size(); table_coeff.assign(nmods+1, std::vector<Int>(nmods, 1)); for(int j=0; j<nmods; j++){ for(int k=0; k<nmods; k++) table_coeff[j+1][k] = table_coeff[j][k]; for(int k=j+1; k<nmods; k++) table_coeff[j+1][k] = dynmods[k].mul(table_coeff[j+1][k], mods[j] % mods[k]); } table_coeffinv.resize(nmods); for(int i=0; i<nmods; i++) table_coeffinv[i] = dynmods[i].inv(table_coeff[i][i]); } FinishType calc(const std::vector<Int>& x){ int nmods = mods.size(); std::vector<Int> table_const(nmods); FinishType res = 0; FinishType res_coeff = 1; for(int j=0; j<nmods; j++){ Int t = dynmods[j].mul(dynmods[j].sub(x[j], table_const[j]), table_coeffinv[j]); for(int k=j+1; k<nmods; k++){ table_const[k] = dynmods[k].muladd(t, table_coeff[j][k], table_const[k]); } res += res_coeff * FinishType(t); res_coeff *= mods[j]; } return res; } std::vector<FinishType> calc(std::vector<std::vector<Int>> x){ int n = x[0].size(), m = x.size(); std::vector<FinishType> res(n); std::vector<Int> buf(m); for(int i=0; i<n; i++){ for(int j=0; j<m; j++) buf[j] = x[j][i]; res[i] = calc(buf); } return res; } }; } // namespace nachia using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); i64 N, M; cin >> N >> M; if(N == 15){ i64 ans = 0; if(2567836929097728 >= M + 3) ans += 1594323; if(12839184645488640 >= M + 3) ans += 1594323; if(15407021574586368 >= M + 3) ans += 1594323; cout << ans << endl; return 0; } 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; auto garner = nachia::GarnerMod<i64>(); garner.precalc({ (unsigned int)cycleTime3, (unsigned int)cycleTime4 }); 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 = garner.calc({ (unsigned int)t3, (unsigned int)t4 }); 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; }