結果

問題 No.2748 Strange Clock
コンテスト
ユーザー Nachia
提出日時 2024-04-20 19:57:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,221 bytes
コンパイル時間 1,750 ms
コンパイル使用メモリ 125,812 KB
最終ジャッジ日時 2025-02-21 07:18:09
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 26 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <array>
#include <cmath>
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
#include <unordered_map>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    i64 N, M; cin >> N >> M;
    unordered_map<i64,vector<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){
        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[sl].push_back(t12);
    }
    i64 ans = 0;
    for(auto& f : T){
        auto t = f.second;
        sort(t.begin(), t.end());
        t.push_back(t.front() + cycleTime);
        rep(i,t.size()-1) if(t[i+1] - t[i] >= M+1) ans += 1;
    }
    cout << ans << endl;
    return 0;
}
0