結果

問題 No.2048 L(I+D)S
コンテスト
ユーザー hitonanode
提出日時 2022-08-09 20:25:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 2,596 bytes
コンパイル時間 1,354 ms
コンパイル使用メモリ 123,848 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-20 00:54:39
合計ジャッジ時間 2,158 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>
using namespace std;
using lint = long long;
template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> int argub(const std::vector<T> &v, const T &x) { return std::distance(v.begin(), std::upper_bound(v.begin(), v.end(), x)); }

#include <atcoder/modint>
using mint = atcoder::modint998244353;

template <typename modint> struct acl_fac {
    std::vector<modint> facs, facinvs;
    acl_fac(int N) {
        assert(-1 <= N and N < modint::mod());
        facs.resize(N + 1, 1);
        for (int i = 1; i <= N; i++) facs[i] = facs[i - 1] * i;
        facinvs.assign(N + 1, facs.back().inv());
        for (int i = N; i > 0; i--) facinvs[i - 1] = facinvs[i] * i;
    }
    modint ncr(int n, int r) const {
        if (n < 0 or r < 0 or n < r) return 0;
        return facs[n] * facinvs[r] * facinvs[n - r];
    }
    modint npr(int n, int r) const {
        if (n < 0 or r < 0 or n < r) return 0;
        return facs[n] * facinvs[n - r];
    }

    modint operator[](int i) const { return facs[i]; }
    modint finv(int i) const { return facinvs[i]; }
};
acl_fac<mint> fac(201010);


int lislen(const vector<int> &a) {
    constexpr int INF = 1 << 30;
    vector<int> dp(a.size() + 2, INF);
    dp[0] = -INF;
    int maxlen = 0;
    for (auto x : a) {
        int i = argub(dp, x);
        dp[i] = x;
        chmax(maxlen, i);
    }
    return maxlen;
}

lint bruteforce(int n, int m) {
    vector<int> A(n + m);
    iota(A.begin(), A.end(), 0);

    lint ret = 0;

    do {
        int u = lislen(A);
        if (u != n) continue;
        vector<int> B;
        for (auto x : A) B.push_back(-x);
        int v = lislen(B);
        if (v == m) ++ret;
    } while (next_permutation(A.begin(), A.end()));

    return sqrtl(ret);
}
// -> https://oeis.org/A059797

// T[n_, k_] := (k + 1)(n + k +4) FactorialPower[k + n + 2, n]/(n! + (n + 1)!)
mint A059797(int n, int k) {
    mint ret = mint(k + 1) * mint(n + k + 4) * (fac[n] + fac[n + 1]).inv();
    ret *= fac.npr(k + n + 2, n);
    return ret;
}

// # of permutation of a = (1, 2, ..., n + m) s.t. len(lis(a)) == n and len(lds(a)) == m
mint solve(int n, int m) {
    if (n <= 1 or m <= 1) return 0;
    return A059797(n - 2, m - 2).pow(2);
}

int main() {
    int N;
    cin >> N;

    mint ret = 0;
    for (int lislen = 0; lislen <= N; ++lislen) {
        int ldslen = N - lislen;
        ret += solve(lislen, ldslen);
    }
    cout << ret.val() << endl;
}
0