#993738 (C++17) No.2802 Pill Bug in Grid Maze

提出ソース

結果

問題	No.2802 Pill Bug in Grid Maze
ユーザー	👑 Nachia
提出日時	2024-07-11 23:55:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	76 ms / 2,000 ms
コード長	5,847 bytes
コンパイル時間	1,242 ms
コンパイル使用メモリ	103,972 KB
実行使用メモリ	6,400 KB
最終ジャッジ日時	2024-07-11 23:55:49
合計ジャッジ時間	3,348 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 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	5 ms 5,376 KB
testcase_08	AC	76 ms 6,400 KB
testcase_09	AC	5 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	5 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	7 ms 5,376 KB
testcase_18	AC	4 ms 5,376 KB
testcase_19	AC	5 ms 5,376 KB
testcase_20	AC	27 ms 5,376 KB
testcase_21	AC	53 ms 5,376 KB
testcase_22	AC	27 ms 5,376 KB
testcase_23	AC	64 ms 5,376 KB
testcase_24	AC	32 ms 5,376 KB
testcase_25	AC	13 ms 5,376 KB
testcase_26	AC	12 ms 5,376 KB
testcase_27	AC	8 ms 5,376 KB
testcase_28	AC	26 ms 5,376 KB
testcase_29	AC	44 ms 5,376 KB
testcase_30	AC	9 ms 5,376 KB
testcase_31	AC	75 ms 5,888 KB
testcase_32	AC	65 ms 5,376 KB
testcase_33	AC	21 ms 5,376 KB
testcase_34	AC	33 ms 5,376 KB

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

ソースコード

raw source code

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <array>
#include <cmath>
#include <atcoder/modint>
#include <bitset>


namespace nachia{

// reference
// https://drive.google.com/file/d/16g1tfSHUU4NXNTDgaD8FSA1WB4FtJCyV/edit
class NimberManager{
private:
    using u32 = unsigned int;
    using u64 = unsigned long long;
    
    std::vector<u32> precalc1;
    void fill_precalc1(){
        precalc1.assign(1 << 16, 0);
        precalc1[(1 << 8) ^ 1] = 1;
        for(int dd=1; dd<8; dd<<=1){
            int d = 1 << dd;
            int c = d >> 1;
            for(int a0=0; a0<d; a0++) for(int a1=0; a1<d; a1++) if(a0 | a1) {
                for(int b0=0; b0<d; b0++) for(int b1=0; b1<d; b1++) if(b0 | b1) {
                    u64 buf = 0;
                    buf ^= precalc1[(a1 << 8) ^ b1];
                    buf ^= precalc1[(a1 << 8) ^ b0];
                    buf ^= precalc1[(a0 << 8) ^ b1];
                    buf <<= dd;
                    buf ^= precalc1[(c << 8) ^ precalc1[(a1 << 8) ^ b1]];
                    buf ^= precalc1[(a0 << 8) ^ b0];
                    precalc1[(((a1 << dd) ^ a0) << 8) ^ ((b1 << dd) ^ b0)] = buf;
                }
            }
        }
    }
    
    u64 product_full(u64 a, u64 b, int d = 6) noexcept {
        if(!(a && b)) return 0;
        if(d == 3){ return precalc1[(a << 8) ^ b]; }
        d--;
        u64 lm = ((u64)1 << (1 << d)) - 1;
        u64 us = ((u64)1 << d);
        u64 buf = 0;
        u64 a1b1 = product_full(a >> us, b >> us, d);
        u64 a2b2 = product_full(a & lm, b & lm, d);
        u64 aabb = product_full((a & lm) ^ (a >> us), (b & lm) ^ (b >> us), d);
        buf ^= (aabb ^ a2b2);
        buf <<= us;
        buf ^= a2b2;
        buf ^= product_full((u64)1 << (us - 1), a1b1, d);
        return buf;
    }
public:
    NimberManager(){ fill_precalc1(); }
    
    unsigned long long product(unsigned long long a, unsigned long long b) noexcept { return product_full(a,b); }
};

} // namespace nachia

namespace nachia{

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x8888'8888;
    constexpr u64 mi = 0x1111'1111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}

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--)
const i64 INF = 1001001001001001001;
const char* yn(bool x){ return x ? "Yes" : "No"; }
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
template<typename A> using nega_queue = std::priority_queue<A,std::vector<A>,std::greater<A>>;
using Modint = atcoder::static_modint<998244353>;

namespace nachia{

template<class Modint>
class Comb{
private:
    std::vector<Modint> F;
    std::vector<Modint> iF;
public:
    void extend(int newN){
        int prevN = (int)F.size() - 1;
        if(prevN >= newN) return;
        F.resize(newN+1);
        iF.resize(newN+1);
        for(int i=prevN+1; i<=newN; i++) F[i] = F[i-1] * Modint::raw(i);
        iF[newN] = F[newN].inv();
        for(int i=newN; i>prevN; i--) iF[i-1] = iF[i] * Modint::raw(i);
    }
    Comb(int n = 1){
        F.assign(2, Modint(1));
        iF.assign(2, Modint(1));
        extend(n);
    }
    Modint factorial(int n) const { return F[n]; }
    Modint invFactorial(int n) const { return iF[n]; }
    Modint invOf(int n) const { return iF[n] * F[n-1]; }
    Modint comb(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return F[n] * iF[r] * iF[n-r];
    }
    Modint invComb(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return iF[n] * F[r] * F[n-r];
    }
    Modint perm(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return F[n] * iF[n-r];
    }
    Modint invPerm(int n, int r) const {
        if(n < 0 || n < r || r < 0) return Modint(0);
        return iF[n] * F[n-r];
    }
    Modint operator()(int n, int r) const { return comb(n,r); }
};

} // namespace nachia
using namespace std;

void testcase(){
    int H, W; cin >> H >> W;
    auto comb = nachia::Comb<Modint>(H+W);
    if(H == 1 || W == 1){ cout << "1\n"; return; }
    Modint ans = 0;
    auto f = [&](i64 k) -> Modint {
        if(k > i64(H) * W) return 0;
        return Modint(2).pow(i64(H)*W - k);
    };
    for(int K=0; K<=W-1; K++){
        auto x = comb(W-1, K);
        auto a = comb(H-2, K);
        auto b = comb(H-2, K-1);
        //cout << x.val() << " " << a.val() << " " << b.val() << endl;
        //cout << (x * a * f(H+W-1+K*2-0)).val() << endl;
        //cout << (x * b * f(H+W-1+K*2-1)).val() << endl;
        ans += x * a * f(H+W-1+K*2-0);
        ans += x * b * f(H+W-1+K*2-1);
    }
    cout << ans.val() << endl;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    testcase();
    return 0;
}

yukicoder

結果

テストケース

ソースコード