結果
| 問題 | No.2857 Div Array |
| コンテスト | |
| ユーザー |
 ecottea
|
| 提出日時 | 2026-01-02 02:01:47 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 18,628 bytes |
| 記録 | |
| コンパイル時間 | 10,986 ms |
| コンパイル使用メモリ | 381,008 KB |
| 実行使用メモリ | 7,852 KB |
| 最終ジャッジ日時 | 2026-01-02 02:02:01 |
| 合計ジャッジ時間 | 13,575 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 28 WA * 2 |
ソースコード
// QCFium 法
//#pragma GCC target("avx2") // yukicoder と codechef では消す
#pragma GCC optimize("O3") // たまにバグる
#pragma GCC optimize("unroll-loops")
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
using mint = modint998244353;
//using mint = static_modint<(int)1e9+7>;
//using mint = modint; // mint::set_mod(m);
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
#endif
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); rep(i,9)cout<<MLE[i]; exit(0); } } // RE の代わりに MLE を出す
#endif
//【畳込み（素朴）】O(n m)
template <class T>
vector<T> naive_convolution(const vector<T>& a, const vector<T>& b) {
int n = sz(a), m = sz(b);
if (n == 0 || m == 0) return vector<T>();
// c[k] = Σ_(i+j=k) a[i] b[j]
vector<T> c(n + m - 1);
if (n < m) {
rep(i, n) rep(j, m) c[i + j] += a[i] * b[j];
}
else {
rep(j, m) rep(i, n) c[i + j] += a[i] * b[j];
}
return c;
}
//【畳込み（法が任意，mint）】O((n + m) log(n + m))（手元ではオーバーフローでバグるので注意）
vm convolution_arbitrary_mod(const vm& a, const vm& b) {
int n = sz(a), m = sz(b);
if (n == 0 || m == 0) return vm();
if (min(n, m) <= 80) {
vm c(n + m - 1);
if (n < m) {
rep(i, n) rep(j, m) c[i + j] += a[i] * b[j];
}
else {
rep(j, m) rep(i, n) c[i + j] += a[i] * b[j];
}
return c;
}
constexpr int MOD = mint::mod();
constexpr int MOD1 = 998244353;
constexpr int MOD2 = 897581057;
constexpr int MOD3 = 880803841;
constexpr __int128 MOD23 = 790592842614439937;
constexpr __int128 MOD13 = 879257460378959873;
constexpr __int128 MOD12 = 896005221510021121;
constexpr __int128 MOD123 = __int128(MOD1) * MOD2 * MOD3; // 789204840662082423367925761
constexpr int MOD23_inv = 41593599;
constexpr int MOD13_inv = 635786105;
constexpr int MOD12_inv = 220201354;
using mint1 = static_modint<MOD1>;
using mint2 = static_modint<MOD2>;
using mint3 = static_modint<MOD3>;
vector<mint1> a1(n), b1(m);
vector<mint2> a2(n), b2(m);
vector<mint3> a3(n), b3(m);
rep(i, n) {
a1[i] = a[i].val();
a2[i] = a[i].val();
a3[i] = a[i].val();
}
rep(j, m) {
b1[j] = b[j].val();
b2[j] = b[j].val();
b3[j] = b[j].val();
}
auto c1 = convolution(a1, b1);
auto c2 = convolution(a2, b2);
auto c3 = convolution(a3, b3);
vm res(n + m - 1);
rep(k, n + m - 1) {
__int128 val1 = c1[k].val() * MOD23 * MOD23_inv;
__int128 val2 = c2[k].val() * MOD13 * MOD13_inv;
__int128 val3 = c3[k].val() * MOD12 * MOD12_inv;
res[k] = (int)(((val1 + val2 + val3) % MOD123) % MOD);
}
return res;
}
//【形式的冪級数】
struct MFPS {
using SMFPS = vector<pim>;
int n; // 係数の個数（次数 + 1）
vm c; // 係数列
inline static vm(*CONV)(const vm&, const vm&) = convolution; // 畳込み用の関数
// コンストラクタ（0，定数，係数列で初期化）
MFPS() : n(0) {}
MFPS(mint c0) : n(1), c({ c0 }) {}
MFPS(int c0) : n(1), c({ mint(c0) }) {}
MFPS(mint c0, int d) : n(d), c(n) { if (n > 0) c[0] = c0; }
MFPS(int c0, int d) : n(d), c(n) { if (n > 0) c[0] = c0; }
MFPS(const vm& c_) : n(sz(c_)), c(c_) {}
MFPS(const vi& c_) : n(sz(c_)), c(n) { rep(i, n) c[i] = c_[i]; }
// 代入
MFPS(const MFPS& f) = default;
MFPS& operator=(const MFPS& f) = default;
MFPS& operator=(const mint& c0) { n = 1; c = { c0 }; return *this; }
void push_back(mint cn) { c.emplace_back(cn); ++n; }
void pop_back() { c.pop_back(); --n; }
[[nodiscard]] mint back() { return c.back(); }
// 比較
[[nodiscard]] bool operator==(const MFPS& g) const { return c == g.c; }
[[nodiscard]] bool operator!=(const MFPS& g) const { return c != g.c; }
// アクセス
inline mint const& operator[](int i) const { return c[i]; }
inline mint& operator[](int i) { return c[i]; }
// 次数
[[nodiscard]] int deg() const { return n - 1; }
[[nodiscard]] int size() const { return n; }
static void set_conv(vm(*CONV_)(const vm&, const vm&)) {
CONV = CONV_;
}
// 加算
MFPS& operator+=(const MFPS& g) {
if (n >= g.n) rep(i, g.n) c[i] += g.c[i];
else {
rep(i, n) c[i] += g.c[i];
repi(i, n, g.n - 1) c.push_back(g.c[i]);
n = g.n;
}
return *this;
}
[[nodiscard]] MFPS operator+(const MFPS& g) const { return MFPS(*this) += g; }
// 定数加算
MFPS& operator+=(const mint& sc) {
if (n == 0) { n = 1; c = { sc }; }
else { c[0] += sc; }
return *this;
}
[[nodiscard]] MFPS operator+(const mint& sc) const { return MFPS(*this) += sc; }
[[nodiscard]] friend MFPS operator+(const mint& sc, const MFPS& f) { return f + sc; }
MFPS& operator+=(const int& sc) { *this += mint(sc); return *this; }
[[nodiscard]] MFPS operator+(const int& sc) const { return MFPS(*this) += sc; }
[[nodiscard]] friend MFPS operator+(const int& sc, const MFPS& f) { return f + sc; }
// 減算
MFPS& operator-=(const MFPS& g) {
if (n >= g.n) rep(i, g.n) c[i] -= g.c[i];
else {
rep(i, n) c[i] -= g.c[i];
repi(i, n, g.n - 1) c.push_back(-g.c[i]);
n = g.n;
}
return *this;
}
[[nodiscard]] MFPS operator-(const MFPS& g) const { return MFPS(*this) -= g; }
// 定数減算
MFPS& operator-=(const mint& sc) { *this += -sc; return *this; }
[[nodiscard]] MFPS operator-(const mint& sc) const { return MFPS(*this) -= sc; }
[[nodiscard]] friend MFPS operator-(const mint& sc, const MFPS& f) { return -(f - sc); }
MFPS& operator-=(const int& sc) { *this += -sc; return *this; }
[[nodiscard]] MFPS operator-(const int& sc) const { return MFPS(*this) -= sc; }
[[nodiscard]] friend MFPS operator-(const int& sc, const MFPS& f) { return -(f - sc); }
// 加法逆元
[[nodiscard]] MFPS operator-() const { return MFPS(*this) *= -1; }
// 定数倍
MFPS& operator*=(const mint& sc) { rep(i, n) c[i] *= sc; return *this; }
[[nodiscard]] MFPS operator*(const mint& sc) const { return MFPS(*this) *= sc; }
[[nodiscard]] friend MFPS operator*(const mint& sc, const MFPS& f) { return f * sc; }
MFPS& operator*=(const int& sc) { *this *= mint(sc); return *this; }
[[nodiscard]] MFPS operator*(const int& sc) const { return MFPS(*this) *= sc; }
[[nodiscard]] friend MFPS operator*(const int& sc, const MFPS& f) { return f * sc; }
// 右からの定数除算
MFPS& operator/=(const mint& sc) { *this *= sc.inv(); return *this; }
[[nodiscard]] MFPS operator/(const mint& sc) const { return MFPS(*this) /= sc; }
MFPS& operator/=(const int& sc) { *this /= mint(sc); return *this; }
[[nodiscard]] MFPS operator/(const int& sc) const { return MFPS(*this) /= sc; }
// 積
MFPS& operator*=(const MFPS& g) { c = CONV(c, g.c); n = sz(c); return *this; }
[[nodiscard]] MFPS operator*(const MFPS& g) const { return MFPS(*this) *= g; }
// 除算
[[nodiscard]] MFPS inv(int d) const {
Assert(!c.empty());
Assert(c[0] != 0);
MFPS g(c[0].inv());
for (int k = 1; k < d; k <<= 1) {
int len = max(min(2 * k, d), 1);
MFPS tmp(0, len);
rep(i, min(len, n)) tmp[i] = -c[i]; // -f
tmp *= g; // -f h
tmp.resize(len);
tmp[0] += 2; // 2 - f h
g *= tmp; // (2 - f h) h
g.resize(len);
}
return g;
}
MFPS& operator/=(const MFPS& g) { return *this *= g.inv(max(n, g.n)); }
[[nodiscard]] MFPS operator/(const MFPS& g) const { return MFPS(*this) /= g; }
// 余り付き除算
[[nodiscard]] MFPS quotient(const MFPS& g) const {
if (n < g.n) return MFPS();
return ((this->rev() / g.rev()).resize(n - g.n + 1)).rev();
}
[[nodiscard]] MFPS reminder(const MFPS& g) const {
return (*this - this->quotient(g) * g).resize();
}
[[nodiscard]] pair<MFPS, MFPS> quotient_remainder(const MFPS& g) const {
pair<MFPS, MFPS> res;
res.first = this->quotient(g);
res.second = (*this - res.first * g).resize();
return res;
}
// スパース積
MFPS& operator*=(const SMFPS& g) {
// g の定数項だけ例外処理
auto it0 = g.begin();
mint g0 = 0;
if (it0->first == 0) {
g0 = it0->second;
it0++;
}
// 後ろからインライン配る DP
repir(i, n - 1, 0) {
// 上位項に係数倍して配っていく．
for (auto it = it0; it != g.end(); it++) {
auto [j, gj] = *it;
if (i + j >= n) break;
c[i + j] += c[i] * gj;
}
// 定数項は最後に配るか消去しないといけない．
c[i] *= g0;
}
return *this;
}
[[nodiscard]] MFPS operator*(const SMFPS& g) const { return MFPS(*this) *= g; }
// スパース商
MFPS& operator/=(const SMFPS& g) {
// g の定数項だけ例外処理
auto it0 = g.begin();
Assert(it0->first == 0 && it0->second != 0);
mint g0_inv = it0->second.inv();
it0++;
// 前からインライン配る DP（後ろに累積効果あり）
rep(i, n) {
// 定数項は最初に配らないといけない．
c[i] *= g0_inv;
// 上位項に係数倍して配っていく．
for (auto it = it0; it != g.end(); it++) {
auto [j, gj] = *it;
if (i + j >= n) break;
c[i + j] -= c[i] * gj;
}
}
return *this;
}
[[nodiscard]] MFPS operator/(const SMFPS& g) const { return MFPS(*this) /= g; }
// 係数反転
[[nodiscard]] MFPS rev() const { MFPS h = *this; reverse(all(h.c)); return h; }
// 単項式
[[nodiscard]] static MFPS monomial(int d, mint coef = 1) {
MFPS mono(0, d + 1);
mono[d] = coef;
return mono;
}
// 不要な高次項の除去
MFPS& resize() {
// 最高次の係数が非 0 になるまで削る．
while (n > 0 && c[n - 1] == 0) {
c.pop_back();
n--;
}
return *this;
}
// x^d 以上の項を除去する．
MFPS& resize(int d) {
n = d;
c.resize(d);
return *this;
}
// 不定元への代入
[[nodiscard]] mint assign(const mint& x) const {
mint val = 0;
repir(i, n - 1, 0) val = val * x + c[i];
return val;
}
// 係数のシフト
MFPS& operator>>=(int d) {
n += d;
c.insert(c.begin(), d, 0);
return *this;
}
MFPS& operator<<=(int d) {
n -= d;
if (n <= 0) { c.clear(); n = 0; }
else c.erase(c.begin(), c.begin() + d);
return *this;
}
[[nodiscard]] MFPS operator>>(int d) const { return MFPS(*this) >>= d; }
[[nodiscard]] MFPS operator<<(int d) const { return MFPS(*this) <<= d; }
#ifdef _MSC_VER
friend ostream& operator<<(ostream& os, const MFPS& f) {
if (f.n == 0) os << 0;
else {
rep(i, f.n) {
os << f[i] << "z^" << i;
if (i < f.n - 1) os << " + ";
}
}
return os;
}
#endif
};
//【線形漸化式の発見】O(n^2)
vm berlekamp_massey(const vm& a) {
vm S(a), C{ 1 }, B{ 1 };
int N = sz(a), m = 1; mint b = 1;
rep(n, N) {
mint d = 0;
rep(i, sz(C)) d += C[i] * S[n - i];
if (d == 0) {
m++;
}
else if (2 * (sz(C) - 1) <= n) {
vm T(C);
mint coef = d * b.inv();
C.resize(max(sz(C), sz(B) + m));
rep(j, sz(B)) C[j + m] -= coef * B[j];
B = T;
b = d;
m = 1;
}
else {
mint coef = d * b.inv();
C.resize(max(sz(C), sz(B) + m));
rep(j, sz(B)) C[j + m] -= coef * B[j];
m++;
}
}
return C;
}
//【展開係数】O(n log n log N)
mint bostan_mori(MFPS f, MFPS g, ll N) {
Assert(g.n >= 1 && g[0] != 0);
// f(z) = 0 のときは 0 を返す．
if (f.n == 0) return 0;
while (N > 0) {
// f2(z) = f(z) g(-z), g2(z) = g(z) g(-z) を求める．
MFPS f2, g2 = g;
rep(i, g2.n) if (i & 1) g2[i] *= -1;
f2 = f * g2;
g2 *= g;
// f3(z) = E(z) or O(z), g3(z) = e(z) を求める．
f.c.clear(); g.c.clear();
if (N & 1) rep(i, min<ll>(f2.n / 2, N / 2 + 1)) f.c.push_back(f2[2 * i + 1]);
else rep(i, min<ll>((f2.n + 1) / 2, N / 2 + 1)) f.c.push_back(f2[2 * i]);
f.n = sz(f.c);
rep(i, min<ll>((g2.n + 1) / 2, N / 2 + 1)) g.c.push_back(g2[2 * i]);
g.n = sz(g.c);
// N を半分にして次のステップに進む．
N /= 2;
}
// N = 0 になったら定数項を返す．
return f[0] / g[0];
}
pair<MFPS, MFPS> get_GF(const vm& seq) {
auto coefs = berlekamp_massey(seq);
frac_print = 1; dump("coefs:", coefs); dump("sz(coefs):", sz(coefs)); frac_print = 0;
MFPS Dnm(coefs);
MFPS Num = (Dnm * MFPS(seq)).resize(sz(coefs));
return { Num, Dnm };
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
//【方法】
// 愚直を書いて集めたデータをもとに線形漸化式を復元し，第 N 項を高速に求める．
//【使い方】
// 1. vm seq[0..N) を用意する．
// 2. [num, dnm] = get_GF(seq) で有理型母関数を復元する．
// 3. bostan_mori(num, dnm, n) で勝手に seq[n] を求めてくれる．
if (mint::mod() != 998244353) {
MFPS::set_conv(naive_convolution);
//MFPS::set_conv(convolution_arbitrary_mod); // 手元ではオーバーフローでバグる
}
ll n; int m, K;
cin >> n >> m >> K;
int N = 20;
vm seq{ m };
vm dp(m + 1);
repi(a, 1, m) dp[m / a]++;
rep(hoge, N) {
vm ndp(m + 1);
repi(j, 1, m) {
repi(a, 1, m) {
int nj = m / a;
if (abs(j - nj) > K) continue;
ndp[nj] += dp[j];
}
}
dp = move(ndp);
seq.push_back(accumulate(all(dp), mint(0)));
}
// dump("seq:", seq);
auto [num, dnm] = get_GF(seq);
mint res = bostan_mori(num, dnm, n - 1);
cout << res << "\n";
}
/*
100 100 38
seq: 100 9618 942424 92360466 67475359 657413226 905489189 899214474 196605706 914260949 311569922 920895343 54411210 235318792 94477621 593475420 25701050 608676129 820228540 36754655 470402880 700732409 815652752 191473738 332050388 251623866 471991744 5069834 861016231 923990480 478817269 212423947 996766446 503192746 574647104 431447991 576040312 601125107 947320652 15401866 814610139 527169816 687668806 158108683 792571599 768869000 776221427 850256020 622205031 117498509 142253193 217351086 471215457 38974697 247970513 431121665 350214147 877227222 323595872 586256085 236775514 511609398 732953228 608123192 853218605
coefs: 1 -100 191 460 -552
sz(coefs): 5
412066770
*/