結果

問題 No.1241 Eternal Tours
ユーザー hitonanodehitonanode
提出日時 2020-09-06 12:28:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 8,632 bytes
コンパイル時間 1,401 ms
コンパイル使用メモリ 94,624 KB
実行使用メモリ 7,000 KB
最終ジャッジ日時 2024-05-06 23:56:41
合計ジャッジ時間 43,274 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 36 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 8 ms
5,376 KB
testcase_09 AC 5 ms
5,376 KB
testcase_10 AC 5 ms
5,376 KB
testcase_11 AC 5 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 5 ms
5,376 KB
testcase_14 WA -
testcase_15 AC 3 ms
5,376 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 71 ms
5,376 KB
testcase_21 AC 561 ms
5,376 KB
testcase_22 WA -
testcase_23 AC 1,974 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 WA -
testcase_29 AC 50 ms
7,000 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 31 ms
5,376 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <chrono>
#include <iostream>
#include <vector>
using namespace std;

// Berlekamp-Massey 解法（与える項の数が足りず想定WA）

template <int mod>
struct ModInt
{
    using lint = long long;
    int val;
    constexpr ModInt() : val(0) {}
    constexpr ModInt &_setval(lint v) { val = (v >= mod ? v - mod : v); return *this; }
    constexpr ModInt(lint v) { _setval(v % mod + mod); }
    explicit operator bool() const { return val != 0; }
    constexpr ModInt operator+(const ModInt &x) const { return ModInt()._setval((lint)val + x.val); }
    constexpr ModInt operator-(const ModInt &x) const { return ModInt()._setval((lint)val - x.val + mod); }
    constexpr ModInt operator*(const ModInt &x) const { return ModInt()._setval((lint)val * x.val % mod); }
    constexpr ModInt operator/(const ModInt &x) const { return ModInt()._setval((lint)val * x.inv() % mod); }
    constexpr ModInt operator-() const { return ModInt()._setval(mod - val); }
    constexpr ModInt &operator+=(const ModInt &x) { return *this = *this + x; }
    constexpr ModInt &operator-=(const ModInt &x) { return *this = *this - x; }
    constexpr ModInt &operator*=(const ModInt &x) { return *this = *this * x; }
    constexpr ModInt &operator/=(const ModInt &x) { return *this = *this / x; }
    friend constexpr ModInt operator+(lint a, const ModInt &x) { return ModInt()._setval(a % mod + x.val); }
    friend constexpr ModInt operator-(lint a, const ModInt &x) { return ModInt()._setval(a % mod - x.val + mod); }
    friend constexpr ModInt operator*(lint a, const ModInt &x) { return ModInt()._setval(a % mod * x.val % mod); }
    friend constexpr ModInt operator/(lint a, const ModInt &x) { return ModInt()._setval(a % mod * x.inv() % mod); }
    constexpr bool operator==(const ModInt &x) const { return val == x.val; }
    constexpr bool operator!=(const ModInt &x) const { return val != x.val; }
    bool operator<(const ModInt &x) const { return val < x.val; }  // To use std::map<ModInt, T>
    friend std::istream &operator>>(std::istream &is, ModInt &x) { lint t; is >> t; x = ModInt(t); return is; }
    friend std::ostream &operator<<(std::ostream &os, const ModInt &x) { os << x.val;  return os; }
    constexpr lint power(lint n) const {
        lint ans = 1, tmp = this->val;
        while (n) {
            if (n & 1) ans = ans * tmp % mod;
            tmp = tmp * tmp % mod;
            n /= 2;
        }
        return ans;
    }
    constexpr ModInt pow(lint n) const {
        return power(n);
    }
    constexpr lint inv() const { return this->power(mod - 2); }
};

constexpr int md = 998244353;
using mint = ModInt<md>;


// Berlekamp–Massey algorithm
// <https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm>
// Complexity: O(N^2)
// input: S = sequence from field K
// return: L          = degree of minimal polynomial,
//         C_reversed = monic min. polynomial (size = L + 1, reversed order, C_reversed[0] = 1))
// Formula: convolve(S, C_reversed)[i] = 0 for i >= L
// Example:
// - [1, 2, 4, 8, 16]   -> (1, [1, -2])
// - [1, 1, 2, 3, 5, 8] -> (2, [1, -1, -1])
// - [0, 0, 0, 0, 1]    -> (5, [1, 0, 0, 0, 0, 998244352]) (mod 998244353)
// - []                 -> (0, [1])
// - [0, 0, 0]          -> (0, [1])
// - [-2]               -> (1, [1, 2])
template <typename Tfield>
std::pair<int, std::vector<Tfield>> linear_recurrence(const std::vector<Tfield> &S)
{
    int N = S.size();
    using poly = std::vector<Tfield>;
    poly C_reversed{1}, B{1};
    int L = 0, m = 1;
    Tfield b = 1;

    // adjust: C(x) <- C(x) - (d / b) x^m B(x)
    auto adjust = [](poly C, const poly &B, Tfield d, Tfield b, int m) -> poly {
        C.resize(std::max(C.size(), B.size() + m));
        Tfield a = d / b;
        for (unsigned i = 0; i < B.size(); i++) C[i + m] -= a * B[i];
        return C;
    };

    for (int n = 0; n < N; n++) {
        Tfield d = S[n];
        for (int i = 1; i <= L; i++) d += C_reversed[i] * S[n - i];

        if (d == 0) m++;
        else if (2 * L <= n) {
            poly T = C_reversed;
            C_reversed = adjust(C_reversed, B, d, b, m);
            L = n + 1 - L;
            B = T;
            b = d;
            m = 1;
        }
        else C_reversed = adjust(C_reversed, B, d, b, m++);
    }
    return std::make_pair(L, C_reversed);
}

// Calculate x^N mod f(x)
// Known as `Kitamasa method`
// Input: f_reversed: monic, reversed (f_reversed[0] = 1)
// Complexity: O(K^2 lgN) (K: deg. of f)
// Example: (4, [1, -1, -1]) -> [2, 3]
//          ( x^4 = (x^2 + x + 2)(x^2 - x - 1) + 3x + 2 )
// Reference: <http://misawa.github.io/others/fast_kitamasa_method.html>
//            <http://sugarknri.hatenablog.com/entry/2017/11/18/233936>
template <typename Tfield>
std::vector<Tfield> monomial_mod_polynomial(long long N, const std::vector<Tfield> &f_reversed)
{
    assert(!f_reversed.empty() and f_reversed[0] == 1);
    int K = f_reversed.size() - 1;
    if (!K) return {};
    int D = 64 - __builtin_clzll(N);
    std::vector<Tfield> ret(K, 0);
    ret[0] = 1;
    auto self_conv = [](std::vector<Tfield> x) -> std::vector<Tfield> {
        int d = x.size();
        std::vector<Tfield> ret(d * 2 - 1);
        for (int i = 0; i < d; i++)
        {
            ret[i * 2] += x[i] * x[i];
            for (int j = 0; j < i; j++) ret[i + j] += x[i] * x[j] * 2;
        }
        return ret;
    };
    for (int d = D; d--;)
    {
        ret = self_conv(ret);
        for (int i = 2 * K - 2; i >= K; i--)
        {
            for (int j = 1; j <= K; j++) ret[i - j] -= ret[i] * f_reversed[j];
        }
        ret.resize(K);
        if ((N >> d) & 1)
        {
            std::vector<Tfield> c(K);
            c[0] = -ret[K - 1] * f_reversed[K];
            for (int i = 1; i < K; i++)
            {
                c[i] = ret[i - 1] - ret[K - 1] * f_reversed[K - i];
            }
            ret = c;
        }
    }
    return ret;
}


template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
    os << '[';
    for (auto v : vec)
        os << v << ',';
    os << ']';
    return os;
}
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl


int main()
{
    int X, Y;
    long long T;
    long long a, b, c, d;
    cin >> X >> Y >> T >> a >> b >> c >> d;
    auto START = std::chrono::system_clock::now();

    T = (T - 1) % (md - 1) + 1;

    long long dist = abs(a - c) + abs(b - d);
    if (dist > T)
    {
        puts("0");
        return 0;
    }

    mint primitive_root = 3;

    mint rx = primitive_root.pow((md - 1) / (1 << (X + 1))), rxi = rx.inv();
    mint ry = primitive_root.pow((md - 1) / (1 << (Y + 1))), ryi = ry.inv();

    mint rxa = rx.pow(a), rxai = rxa.inv();
    mint ryb = ry.pow(b), rybi = ryb.inv();

    mint rxc = rx.pow(c), rxci = rxc.inv();
    mint ryd = ry.pow(d), rydi = ryd.inv();

    mint rxpow = 1, rxpowi = 1, rypow, rypowi;
    mint rxapow = 1, rxapowi = 1, rybpow, rybpowi;
    mint rxcpow = 1, rxcpowi = 1, rydpow, rydpowi;

    vector<mint> coeffs;
    vector<mint> fkls;

    for (int k = 0; k < 1 << X; k++)
    {
        rypow = 1, rypowi = 1;
        rybpow = 1, rybpowi = 1;
        rydpow = 1, rydpowi = 1;
        for (int l = 0; l < 1 << Y; l++)
        {
            fkls.emplace_back(rxpow + rxpowi + rypow + rypowi + 1);
            coeffs.emplace_back((rxapow - rxapowi) * (rybpow - rybpowi) * (rxcpow - rxcpowi) * (rydpow - rydpowi) * mint(1 << (X + Y + 2)).inv());

            rypow *= ry, rypowi *= ryi;
            rybpow *= ryb, rybpowi *= rybi;
            rydpow *= ryd, rydpowi *= rydi;
        }
        rxpow *= rx, rxpowi *= rxi;
        rxapow *= rxa, rxapowi *= rxai;
        rxcpow *= rxc, rxcpowi *= rxci;
    }
    vector<mint> fklpow;
    dbg(dist);
    dbg(T);
    for (auto x : fkls) fklpow.emplace_back(x.pow(dist));
    vector<mint> seq;

    for (long long t = dist; t - dist <= 10000; t++)
    {
        if (chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - START).count() > 2000) break;
        mint tmp = 0;
        for (int kl = 0; kl < 1 << (X + Y); kl++) {
            tmp += coeffs[kl] * fklpow[kl];
            fklpow[kl] *= fkls[kl];
        }
        if (t == T)
        {
            cout << tmp << '\n';
            return 0;
        }
        seq.emplace_back(tmp);
    }

    dbg(seq.size());

    auto [L, poly_reversed] = linear_recurrence(seq);

    dbg(L);

    auto g = monomial_mod_polynomial(T - dist, poly_reversed);
    mint ret = 0;
    for (int i = 0; i < int(g.size()); i++) ret += seq.at(i) * g.at(i);

    cout << ret << '\n';
}
0