#966731 (C++17) No.2711 Connecting Lights

提出ソース

結果

問題	No.2711 Connecting Lights
ユーザー	👑 Nachia
提出日時	2024-03-31 13:59:07
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 5,000 ms
コード長	9,989 bytes
コンパイル時間	4,274 ms
コンパイル使用メモリ	174,792 KB
実行使用メモリ	6,548 KB
最終ジャッジ日時	2024-03-31 13:59:23
合計ジャッジ時間	5,136 ms
ジャッジサーバーID （参考情報）	judge10 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	2 ms 6,548 KB
testcase_03	AC	1 ms 6,548 KB
testcase_04	AC	2 ms 6,548 KB
testcase_05	AC	2 ms 6,548 KB
testcase_06	AC	2 ms 6,548 KB
testcase_07	AC	2 ms 6,548 KB
testcase_08	AC	2 ms 6,548 KB
testcase_09	AC	2 ms 6,548 KB
testcase_10	AC	2 ms 6,548 KB
testcase_11	AC	3 ms 6,548 KB
testcase_12	AC	2 ms 6,548 KB
testcase_13	AC	2 ms 6,548 KB
testcase_14	AC	2 ms 6,548 KB
testcase_15	AC	2 ms 6,548 KB
testcase_16	AC	2 ms 6,548 KB
testcase_17	AC	2 ms 6,548 KB
testcase_18	AC	2 ms 6,548 KB
testcase_19	AC	2 ms 6,548 KB
testcase_20	AC	2 ms 6,548 KB
testcase_21	AC	2 ms 6,548 KB
testcase_22	AC	2 ms 6,548 KB
testcase_23	AC	2 ms 6,548 KB
testcase_24	AC	2 ms 6,548 KB
testcase_25	AC	2 ms 6,548 KB
testcase_26	AC	2 ms 6,548 KB
testcase_27	AC	2 ms 6,548 KB
testcase_28	AC	2 ms 6,548 KB
testcase_29	AC	3 ms 6,548 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>
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>;
//#include "nachia/vec.hpp"
using namespace std;


// (edited) Nyaan's library

namespace nachia{

// output : denominator of rational gf
template <typename Modint>
std::vector<Modint> BerlekampMassey(const std::vector<Modint> &s){
    const int N = (int)s.size();
    std::vector<Modint> b, c;
    b.reserve(N+1);
    c.reserve(N+1);
    const Modint Zero = Modint(0);
    const Modint One = Modint(1);
    b.push_back(One);
    c.push_back(One);
    Modint y = One;
    for(int ed=1; ed<=N; ed++){
        int l = int(c.size());
        int m = int(b.size());
        Modint x = Zero;
        for(int i=0; i<l; i++) x += c[i] * s[ed-l+i];
        b.push_back(Zero);
        m++;
        if(x.val() == 0) continue;
        Modint freq = x / y;
        if(l < m){
            auto tmp = c;
            c.insert(c.begin(), m-l, Zero);
            for(int i=0; i<m; i++) c[i] -= freq * b[i];
            std::swap(b, tmp); y = x;
        } else {
            for(int i=0; i<m; i++) c[l-m+i] -= freq * b[i];
        }
    }
    std::reverse(c.begin(), c.end());
    return c;
}

} // namespace nachia
#include <atcoder/convolution>
#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

namespace nachia{

template<class Modint, unsigned int nttmod> std::vector<unsigned int>
    PartConvolution(std::vector<Modint> A, std::vector<Modint> B)
{
    std::vector<atcoder::static_modint<nttmod>> AA(A.size());
    for(std::size_t i=0; i<A.size(); i++) AA[i] = A[i].val();
    std::vector<atcoder::static_modint<nttmod>> BB(B.size());
    for(std::size_t i=0; i<B.size(); i++) BB[i] = B[i].val();
    auto AB = atcoder::convolution(AA, BB);
    std::vector<unsigned int> res(AB.size());
    for(std::size_t i=0; i<AB.size(); i++) res[i] = AB[i].val();
    return res;
}

template<class Modint>
std::vector<Modint> Convolution(std::vector<Modint> A, std::vector<Modint> B){
    auto Q1 = PartConvolution<Modint, 998244353>(A, B);
    auto Q2 = PartConvolution<Modint, 897581057>(A, B);
    auto Q3 = PartConvolution<Modint, 880803841>(A, B);
    GarnerMod<Modint> garner;
    garner.precalc({ 998244353, 897581057, 880803841 });
    return garner.calc({ Q1, Q2, Q3 });
}

} // namespace nachia

namespace nachia{

template<class Modint>
Modint KthTermOfRationalGF(
    std::vector<Modint> denom,
    std::vector<Modint> numer,
    unsigned long long K
){
    assert(denom.size() != 0);
    assert(denom.size() == numer.size());
    assert(denom[0].val() != 0);
    int n = (int)denom.size();
    while(K != 0){
        auto Qn = denom;
        Qn.push_back(Modint(0));
        for(int i=1; i<n; i+=2) Qn[i] = -Qn[i];
        int f = K % 2;
        denom = Convolution(denom, Qn);
        for(int i=0; i<n; i++) denom[i] = denom[i*2];
        denom.resize(n);
        numer = Convolution(numer, Qn);
        for(int i=0; i<n; i++) numer[i] = numer[i*2+f];
        numer.resize(n);
        K /= 2;
    }
    return numer[0] / denom[0];
}

// divisor of fractional representation
//   and first terms
template<class Modint>
Modint KthTermOfLinearRecurrence(
    std::vector<Modint> denom,
    std::vector<Modint> firstTerms,
    unsigned long long K
){
    assert(denom.size() <= firstTerms.size());
    firstTerms.resize(denom.size());
    auto numer = Convolution(firstTerms, denom);
    numer.resize(denom.size());
    return KthTermOfRationalGF(std::move(denom), std::move(numer), K);
}

} // namespace nachia

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

void testcase(){
    int N,M,K; cin >> N >> M >> K;
    if(M == 1){ cout << Modint(2).pow(N).val() << '\n'; return; }
    auto comb = nachia::Comb<Modint>(N);
    int Z = (N+1)*2+1;
    vector<Modint> A(Z); {
        vector<Modint> dp(N+1);
        dp[N] = 1;
        rep(z,Z){
            vector<Modint> nx(N+1);
            rep(i,N+1) rep(j,i+1) if(K<=j) rep(k,N-i+1){
                nx[j+k] += comb(i,j) * comb(N-i,k) * dp[i];
            }
            swap(dp, nx);
            rep(i,N+1) A[z] += dp[i];
        }
    }
    auto rec = nachia::BerlekampMassey(A);
    auto ans = nachia::KthTermOfLinearRecurrence(rec, A, M-1);
    cout << ans.val() << '\n';
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef NACHIA
    int T; cin >> T; for(int t=0; t<T; T!=++t?(cout<<'\n'),0:0)
    #endif
    testcase();
    return 0;
}

yukicoder

結果

テストケース

ソースコード