#435311 (C++17) No.997 Jumping Kangaroo

提出ソース

結果

問題	No.997 Jumping Kangaroo
ユーザー	ganmodokix
提出日時	2020-02-27 23:17:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	9,962 bytes
コンパイル時間	3,054 ms
コンパイル使用メモリ	227,448 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-10-13 16:04:23
合計ジャッジ時間	3,870 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	AC	1 ms 6,820 KB
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	AC	1 ms 6,816 KB
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	2 ms 6,820 KB
testcase_27	AC	2 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// May this submission get accepted
#include <bits/stdc++.h>

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using namespace std;

// エイリアス (補完・コンパイルが重くなる)
// #include <boost/multiprecision/cpp_int.hpp>
// using mll = boost::multiprecision::cpp_int;

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define STEP(i, is, ie, step) for (long long i=(is), i##_end=(ie), i##_step = (step); i<=i##_end; i+=i##_step)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define FOREACH(i,q) for (auto &i : q)
template<class T> bool chmax(T &a, const T b) { if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T b) { if (a > b) {a = b; return true;} return false; }
constexpr int INF = numeric_limits<int>::max();
constexpr long long LINF = numeric_limits<long long>::max();
#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")
#define DUMP(q) DUMP_FUNC(q, #q, __FILE__, __LINE__)
template <typename T> void DUMP_PROC(T x) { cerr << x; }
void DUMP_PROC(string x) { cerr << '"' << x << '"'; }
template <typename T> void DUMP_PROC(vector<T> x) { cerr << "["; for (auto &xi : x) { DUMP_PROC(xi); cerr << (&xi != &*x.rbegin()?", ":""); } cerr << "]"; }
template <typename T> void DUMP_FUNC(T x, const char* name, const char* fn, int ln) { cerr << "\e[32m[DEBUG]\e[0m " << name << ": "; DUMP_PROC(x); cerr << " @ " << fn << "(" << ln << ")" << endl; }
template<class T> T gcd(T a, T b) { if (a < b) swap(a, b); while (b) swap(a %= b, b); return a; }
template<class T> T lcm(const T a, const T b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// 標準入出力
struct inp {
    size_t sz;
    inp(size_t _sz = 1) : sz(_sz) {}
    template <typename T> operator T () const { T a; cin >> a; return a; }
    template <typename T> operator vector<T> () const { vector<T> a(sz); for (size_t i = 0; i < sz; i++) cin >> a[i]; return a; }
    template <typename T, typename U> operator pair<T, U> () const { T f; U s; cin >> f >> s; return pair<T, U>(f, s); }
};
inp inp1; // input one
template <typename T> void say(const T x, const char* end = "\n") { cout << x << end; }
void say(const ld x, const char* end = "\n") { cout << setprecision(30) << x << end; }
template <typename T> void say(const vector<T> x, const char* sep = " ", const char* end = "\n") { REP(i, x.size()) { cout << x[i] << (i+1 == i_len ? end : sep); } }
template <typename T> void say(const vector<vector<T>> x, const char* sep = " ", const char* end = "\n") { REP(i, x.size()) { say(x[i], sep, end); } }

// モジュール

// 精度に寄りけりだがconv1回で済むFFTの方がいい場合もあることに留意
// Cooley-Tukey型 高速フーリエ変換 O(NlogN)
template <ll pdiv = 998244353, ll prim = 3>
vector<ll> ntt(vector<ll> a, const bool inv = false) {

    const auto modpow = [](ll a, ll n) -> ll {
        ll r = 1;
        ((n %= pdiv-1) += pdiv-1) %= pdiv-1;
        for (ll b = (a % pdiv + pdiv) % pdiv; n; n >>= 1, (b *= b) %= pdiv) {
            if (n & 1) (r *= b) %= pdiv;
        }
        return r;
    };

    // Shita-goshirae
    ll n = 1, h = 0;
    while (n < a.size()) n <<= 1, h++;
    a.resize(n, 0);
    for (size_t i = 0; i < n; i++) {
        ((a[i] %= pdiv) += pdiv) %= pdiv;
    }

    // Cooley-Tukey sort
    for (size_t i = 0; i < n; i++) {
        size_t j = 0;
        for (size_t k = 0; k < h; k++) {
            j |= (i >> k & 1) << (h-1 - k);
        }
        if (i < j) swap(a[i], a[j]);
    }

    // butterfly diagram
    for (size_t b = 1; b < n; b <<= 1) {
        const ll root = modpow(prim, (pdiv-1) / (b << 1) * (inv ? -1 : 1));
        ll w = 1;
        for (size_t j = 0; j < b; j++) {
            for (size_t k = 0; k < n; k += b << 1) {
                ll s = a[j+k  ];
                ll t = a[j+k+b] * w % pdiv;
                a[j+k  ] = (s+t) % pdiv;
                a[j+k+b] = (s-t + pdiv) % pdiv;
            }
            (w *= root) %= pdiv;
        }
    }

    if (inv) {
        ll invn = modpow(n, pdiv-2);
        for (ll i = n; i--; ) (a[i] *= invn) %= pdiv;
    }
    
    return a;

}
// 適切な原始根の存在する法での畳み込み
template <ll pdiv = 998244353, ll prim = 3>
vector<ll> convolve_p(const vector<ll> &x, const vector<ll> &y) {
    size_t t = x.size() + y.size() - 1;
    auto a = x; a.resize(t, 0);
    auto b = y; b.resize(t, 0);
    auto A = ntt<pdiv, prim>(a);
    auto B = ntt<pdiv, prim>(b);
    for (size_t i = 0; i < A.size(); i++) (A[i] *= B[i]) %= pdiv;
    auto result = ntt<pdiv, prim>(A, true);
    result.resize(t);
    return result;
}
// 任意MODでの畳み込み演算
vector<ll> convolve(const vector<ll> &x, const vector<ll> &y, const ll pdiv) {

    if (pdiv == 998244353) return convolve_p<998244353, 3>(x, y);

    // 1. 配列の大きさが 2^23 ~= 8e6 超えたら1の2^N乗根求まらなくてバグる
    //   競プロならO(N)すらTLEしかねないから大丈夫
    //   conv2をコメントアウトするとこの上限が2^24 ~= 1.6e7ほどに伸びる
    // 2. 答えの大きさが Πm ~= 9.6e34 超えたらGarnerがバグる
    //   すなわち配列x, yの各項が √(Πm/2^23) ~= 1e14 超えてるとバグる
    //   競プロなら大抵法が1e9くらいなので大丈夫
    //   conv2をコメントアウトすると上限が 2.398e9 ほどになるが1e9+7とかならセーフ
    // 3. 出典: https://lumakernel.github.io/ecasdqina/math/FFT/NTT
    //     {1224736769, 3}, // 2^24 * 73 + 1
    //     {998244353, 3},  // 2^23 * 7 * 17 + 1
    //     {469762049, 3},  // 2^26 * 7 + 1
    //     {167772161, 3},  // 2^25 * 5 + 1
    const auto conv1 = convolve_p<1224736769, 3>(x, y);
    // const auto conv2 = convolve_p<998244353, 3>(x, y);
    const auto conv3 = convolve_p<469762049, 3>(x, y);
    const auto conv4 = convolve_p<167772161, 3>(x, y);

    const auto garner = [&](const vector<pair<ll, ll>> &w) -> ll {
        const auto modpow = [](ll a, ll n, ll pdiv) -> ll {
            ll r = 1;
            ((n %= pdiv-1) += pdiv-1) %= pdiv-1;
            for (ll b = (a % pdiv + pdiv) % pdiv; n; n >>= 1, (b *= b) %= pdiv) {
                if (n & 1) (r *= b) %= pdiv;
            }
            return r;
        };
        vector<ll> p(w.size()+1, 1);
        vector<ll> v(w.size()+1, 0);
        for (size_t k = 0; k < w.size(); k++) {
            ll t = (w[k].first - v[k]) * modpow(p[k], w[k].second-2, w[k].second);
            ((t %= w[k].second) += w[k].second) %= w[k].second;
            for (size_t i = k+1; i <= w.size(); i++) {
                ll bi = i == w.size() ? pdiv : w[i].second;
                (v[i] += t * p[i]) %= bi;
                (p[i] *= w[k].second) %= bi;
            }
        }
        return v.back();
    };

    ll n = conv1.size();
    ll t = x.size() + y.size() - 1;
    vector<ll> result(t, 0);
    REP(i, t) {
        vector<pair<ll, ll>> g = {
            {conv1[i], 1224736769},
            // {conv2[i], 998244353},
            {conv3[i], 469762049},
            {conv4[i], 167772161}
        };
        result[i] = garner(g);
    }
    return result;

}
// 形式的冪級数の逆元のdeg項まで(deg-1次の項まで)を返す
vector<ll> formalinv(const vector<ll> &x, ll deg, ll pdiv) {
    assert(x.front() != 0);
    const auto modpow = [&](ll a, ll n) -> ll {
        ll r = 1;
        ((n %= pdiv-1) += pdiv-1) %= pdiv-1;
        for (ll b = (a % pdiv + pdiv) % pdiv; n; n >>= 1, (b *= b) %= pdiv) {
            if (n & 1) (r *= b) %= pdiv;
        }
        return r;
    };
    const auto modinv = [&](ll a) { return modpow(a, pdiv-2); };
    vector<ll> rs = {modinv(x[0])};
    for (size_t i = 1; i < deg; i *= 2) {
        auto rs2 = rs; for (ll &rsi : rs2) (rsi *= 2) %= pdiv;
        auto rss = convolve(rs, rs, pdiv);
        vector<ll> as(i*2, 0);
        REP(j, min<ll>(i*2, x.size())) as[j] = (x[j] % pdiv + pdiv) % pdiv;
        auto rcv = convolve(rss, as, pdiv);
        rs .resize(i*2, 0);
        rs2.resize(i*2, 0);
        rcv.resize(i*2, 0);
        for (size_t j = 0; j < i*2; j++) {
            rs[j] = (rs2[j] - rcv[j] + pdiv) % pdiv;
        }
    }
    return rs;
}

// 処理内容
int main() {
    
    ios::sync_with_stdio(false); // stdioを使うときはコメントアウトすること
    cin.tie(nullptr);            // インタラクティブ問題ではコメントアウトすること
    
    constexpr ll pdiv = 998244353;

    ll n = inp1;
    ll w = inp1;
    ll k = inp1;
    vector<ll> a = inp(n);

    vector<ll> dp(w*2+1, 0);
    dp[0]++;
    for (ll ai : a) dp[ai]--;
    dp = formalinv(dp, w*2+1, pdiv);

    ll dp1 = dp[w];
    ll dp2 = (dp[w*2] - dp1*dp1%pdiv + pdiv) % pdiv;

    ll m[2][2] = {};

    auto mtrprod = [&](vector<vector<ll>> a, vector<vector<ll>> b) {
        vector<vector<ll>> r = {{0, 0}, {0, 0}};
        REP(i, 2) REP(j, 2) REP(k, 2) (r[i][j] += a[i][k] * b[k][j] % pdiv) %= pdiv;
        return r;
    };

    auto mtrpow = [&](vector<vector<ll>> a, ll n) -> vector<vector<ll>> {
        vector<vector<ll>> r = {{1, 0}, {0, 1}};
        for (vector<vector<ll>> b = a; n; n >>= 1) {
            if (n & 1) {
                r = mtrprod(r, b);
            }
            b = mtrprod(b, b);
        }
        return r;
    };

    vector<vector<ll>> d = {
        {dp1, dp2},
        {  1,   0}
    };
    d = mtrpow(d, k);

    // DUMP(d);

    say(d[0][0]);

}

yukicoder

結果

テストケース

ソースコード