[Medium] CF1821F Timber

简要题意

你需要在数轴上的区间 $[1,n]$ 放 $m$ 棵高度为 $k$ 的树，使得你可以为每一个树钦定一个倾倒方向（左或右），使得所有树均倾倒后，每个数轴上的点至多被一个树覆盖，且不在区间 $[1,n]$ 的点不会被树覆盖。

求方案数，答案对 $998,244,353$ 取模。

$1\leq n,m,k\leq 3\times 10^5$。

思路

考虑到我们本质上相当于将数轴分成 $m$ 段，钦定每一段的后缀被树覆盖，其余部分未被树覆盖。求方案数。

对于一个大小 $\leq k$ 的段，显然是没有方案的。但是对于其余的段可能很复杂，可能会算重。由于方案之和我们选择的树的位置有关，所以不妨假设每个树尽量往左倒。则对于大小 $\geq 2k+1$ 的段，只能让树放在段的末尾，然后钦定往左倒。至于介于 $[k+1,2k]$ 的段，可以在中间往右倒（左侧空间不够），也可以在末尾往左倒，有两种方案。

于是可以列出生成函数：

$$\begin{aligned} &\left(\sum_{j=k+1}^{2k}2z^j+\sum_{j\geq 2k+1} z^j\right)^m\\ &=\left(2z^{k+1}\frac{1-z^{k}}{1-z}+\frac{z^{2k+1}}{1-z}\right)^m\\ &=\left(z^{k+1}\frac{2-z^k}{1-z}\right)^m \end{aligned}$$

所以其实我们就是要求：

$$\left(z^{k+1}\frac{2-z^{k}}{1-z}\right)^{m}$$

多项式乘法（这个 $1-z$ 可以手算逆） & 多项式求 $\ln$ & 多项式求 $\exp$ 应该可以做到 $O(n\log n)$，不过常数过大。

稍微整理一下：

$$z^{(k+1)m}\left(\frac{2-z^{k}}{1-z}\right)^{m}$$

考虑分子分母。

对于分子，有：

$$(2-z^{k})^m=\sum_{i\geq 0}\binom{m}{i}(-1)^{i}z^{ik}2^{m-i}$$

对于分母，有：

$$(1-z)^{-m}=\sum_{i\geq 0}\binom{-m}{i}(-1)^{i}z^{i}=\sum_{i\geq 0}\binom{m+i-1}{i}z^i$$

由于我们只需要取上两式卷积取一个区间的次数，直接对一个多项式的系数取前缀和，然后暴力卷积求一项即可。时间复杂度 $O(n)$。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

const int N = 6e5 + 5;
int n, m, k, fact[N], inv[N], f[N], g[N], pw2[N];

int binom(int n, int m){ return n < m ? 0 : Mul(fact[n], Mul(inv[m], inv[n - m])); }

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    fact[0] = fact[1] = inv[0] = inv[1] = pw2[0] = 1, pw2[1] = 2;
    for(int i=2;i<=n+m;i++){
        fact[i] = Mul(fact[i - 1], i);
        inv[i] = Mul(inv[mod % i], mod - mod / i);
        pw2[i] = Add(pw2[i - 1], pw2[i - 1]);
    }
    for(int i=2;i<=n;i++) inv[i] = Mul(inv[i - 1], inv[i]);
    if(1ll * (k + 1) * m > n) return cout << 0 << '\n', 0;
    int p = n - (k + 1) * m, ans = 0;
    for(int i=0;i<=min(m,p/k);i++) f[i * k] = Mul(binom(m, i), Mul((i & 1) ? mod - 1 : 1, pw2[m - i]));
    g[0] = binom(m - 1, 0);
    for(int i=1;i<=n;i++) g[i] = Add(g[i - 1], binom(m + i - 1, i));
    for(int i=0;i<=p;i++) ans = Add(ans, Mul(f[i], g[p - i]));
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。