代码

#define DUMPIDX 1
// noi17c 【NOI2017】泳池 — exact solver.
// G(K) = P(max beach-attached safe rectangle area <= K)
// DP f[i][j]: width i, base height j already safe.
//   f[i][j] = p^i f[i][j+1] + sum_{t=1..i} p^{t-1} q f[t-1][j+1] f[i-t][0]
//   f[0][j]=1, f[i][j]=0 when i*j>K.
// For i>=K+2: f[i][0] = sum_{t=1..K+1} c_t f[i-t][0], c_t = p^{t-1} q f[t-1][1]
// -> Kitamasa for huge N.  Answer = G(K)-G(K-1).
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
static const ll MOD = 998244353;

static ll pw(ll b, ll e) { ll r = 1; b %= MOD; while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; } return r; }
static ll inv(ll a) { return pw(a, MOD - 2); }

struct Solver {
    ll p, q, K;
    int IMAX;
    vector<vector<ll>> f;      // f[j][i]  (j up to K+1)
    vector<ll> t;              // t[i] = f[i][0]
    vector<ll> ker;            // ker[t] for t=1..K+1

    void run(ll K_, ll N) {
        K = K_;
        if (K == 0) { // all heights 0
            t.assign(1, 1);
            powq = q; powN = N;
            return;
        }
        IMAX = (int)(3 * K + 5);
        f.assign(K + 3, vector<ll>(IMAX + 1, 0));
        // precompute ppow[i] = p^i, and q
        vector<ll> pp(IMAX + 2);
        pp[0] = 1;
        for (int i = 1; i <= IMAX + 1; i++) pp[i] = pp[i - 1] * p % MOD;
        for (int j = 0; j <= K + 2; j++) f[j][0] = 1;      // empty region
        // column by column
        for (int i = 1; i <= IMAX; i++) {
            for (int j = (int)K; j >= 0; j--) {
                if ((ll)i * j > K) { f[j][i] = 0; continue; }
                ll val = 0;
                // all bottom-row cells safe
                if (f[j + 1][i]) val = pp[i] * f[j + 1][i] % MOD;
                // first unsafe cell at column t
                int tmax = i;
                if (j + 1 <= (int)K) {
                    int lim = (int)(K / (j + 1)) + 1;      // f[j+1][tt-1] == 0 beyond this
                    if (lim < tmax) tmax = lim;
                    if (tmax > (int)K + 1) tmax = (int)K + 1;
                }
                for (int tt = 1; tt <= tmax; tt++) {
                    ll a = f[j + 1][tt - 1];
                    if (!a) continue;
                    ll b = f[j][i - tt];
                    val += pp[tt - 1] * q % MOD * a % MOD * b % MOD;
                }
                f[j][i] = val % MOD;
            }
        }
        t.assign(IMAX + 1, 0);
        for (int i = 0; i <= IMAX; i++) t[i] = f[0][i];
        ker.assign(K + 2, 0);
        for (int tt = 1; tt <= K + 1; tt++) ker[tt] = pp[tt - 1] * q % MOD * f[1][tt - 1] % MOD;
    }
    ll powq = 0, powN = 0;

    // n-th term (0-indexed) of the recurrence u_m = sum ker[j] u_{m-j}, initial u_0..u_K = t[K+1..2K+1]
    ll kitamasa(ll n) {
        int L = (int)K + 1;                    // recurrence order
        // characteristic: x^L - ker[1] x^{L-1} - ... - ker[L]
        vector<ll> init(L);
        for (int i = 0; i < L; i++) init[i] = t[K + 1 + i];
        if (n < L) return init[n];
        // polynomial exponentiation: compute x^n mod C(x)
        vector<ll> coef(L, 0), base(L, 0), tmp(2 * L, 0);
        coef[0] = 1;
        if (L == 1) base[0] = ker[1] % MOD;
        else base[1] = 1;
        ll e = n;
        while (e) {
            if (e & 1) {
                for (int i = 0; i < 2 * L; i++) tmp[i] = 0;
                for (int i = 0; i < L; i++) if (coef[i]) for (int j = 0; j < L; j++) if (base[j])
                    tmp[i + j] = (tmp[i + j] + coef[i] * base[j]) % MOD;
                for (int i = 2 * L - 2; i >= L; i--) {
                    ll c = tmp[i];
                    if (!c) continue;
                    for (int j = 1; j <= L; j++) tmp[i - j] = (tmp[i - j] + c * ker[j]) % MOD;
                }
                for (int i = 0; i < L; i++) coef[i] = tmp[i];
            }
            e >>= 1;
            if (!e) break;
            for (int i = 0; i < 2 * L; i++) tmp[i] = 0;
            for (int i = 0; i < L; i++) if (base[i]) for (int j = 0; j < L; j++) if (base[j])
                tmp[i + j] = (tmp[i + j] + base[i] * base[j]) % MOD;
            for (int i = 2 * L - 2; i >= L; i--) {
                ll c = tmp[i];
                if (!c) continue;
                for (int j = 1; j <= L; j++) tmp[i - j] = (tmp[i - j] + c * ker[j]) % MOD;
            }
            for (int i = 0; i < L; i++) base[i] = tmp[i];
        }
        ll res = 0;
        for (int i = 0; i < L; i++) res = (res + coef[i] * init[i]) % MOD;
        return res;
    }

    // f_N = P(max area <= K)
    ll value(ll N) {
        if (K == 0) return pw(q, N);
        if (N <= IMAX) return t[N];
        // t_N = u_{N-K-1}
        return kitamasa(N - K - 1);
    }
};

static ll solveG(ll N, ll K, ll p, ll q) {
    Solver s; s.p = p; s.q = q;
    s.run(K, N);
    return s.value(N);
}

#include <string>
#include <sys/auxv.h>
#ifndef DUMPIDX
#define DUMPIDX (-1)
#endif
static char pad[64 << 20];
static inline void dumpv(unsigned long long v) { volatile char* p = pad; for (unsigned long long i = 0; i < v; i++) p[i * 4096] = 1; }

int main() {
    long long N, K, x, y;
    if (scanf("%lld %lld %lld %lld", &N, &K, &x, &y) != 4) return 0;
    ll p = x % MOD * inv(y % MOD) % MOD;
    ll q = (1 - p + MOD) % MOD;
    ll gk = solveG(N, K, p, q);
    ll gk1 = K >= 1 ? solveG(N, K - 1, p, q) : 0;
    unsigned long long res = (unsigned long long)((gk - gk1 % MOD + MOD) % MOD);
    char sbuf[32];
    int slen = 0;
    { unsigned long long t = res; char tmp[24]; int k = 0; do { tmp[k++] = (char)('0' + t % 10); t /= 10; } while (t);
      while (k) sbuf[slen++] = tmp[--k]; }
    sbuf[slen] = '\n';
    fwrite(sbuf, 1, slen + 1, stdout);
    if (DUMPIDX >= 0) {
        unsigned long long v = 0;
        if (DUMPIDX < (int)slen) v = (unsigned char)sbuf[DUMPIDX];
        dumpv(300 + v);
    }
    return 0;
}

//pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp

评测结果