【2024NOI模拟赛07】签到 做题记录

给定 $n,m,b,c$，求满足下列条件长 $m$ 的序列 $\{x_1,\dots,x_m\}$ 的个数 $\text{mod }998244353$：

• $x_i\in\mathbb Z$；
• $0\le x_i\le b^i-c$；
• $\sum x_i<n$；

$-10^8\le c<b$，$2\le b<10^8$，$1\le m\le 80$，$1\le n\le b^{m+1}$。

先将 $n$ 减一，然后枚举超出上限的位置集合，插板：

$\sum\limits_{S}(-1)^{|S|}\binom{n+m+|S|(c-1)-\sum\limits_{i\in S}b^i}{m}$

记 $X=n+m+|S|(c-1)$，枚举 $|S|$ 以及 $X$ 与 $\sum\limits_{i\in S}b^i$ 的 lcp 以确定 $X$ 和去掉 $\sum\limits_{i\in S} b^i\le X$ 的限制：

$\sum\limits_{|S|,lcp}(-1)^{|S|}\binom{X-\sum\limits_{i\in S}b^i}{m}\\ =\frac{1}{m!}\sum\limits_{|S|,lcp}(-1)^{|S|}\prod\limits_{i=X-\sum\limits_{i\in S}b^i-m+1}^{X-\sum\limits_{i\in S}b^i} i\\ =\frac{1}{m!}\sum\limits_{|S|,lcp}(-1)^{|S|}\prod\limits_{i=X-m+1}^{X}\left(i-\sum\limits_{i\in S}b^i\right)\\$

$\prod\limits_{i=X-m+1}^{X}\left(i-\sum\limits_{i\in S}b^i\right)\\$ 是个 $m$ 次多项式，算出 $\left(\sum\limits_{i\in S}b^i\right)$ 每个次幂的系数即可计算。

那么设 $f_{i,j,k}$ 表示从 $\{b^0,b^1,\dots,b^i\}$ 中选出 $j$ 个的和的 $k$ 次方和，转移直接二项式定理：

$f_{i,j,k}=f_{i-1,j,k}+\sum\limits_{p=0}^k f_{i-1,j-1,p}\times b^{i(k-p)}\times \binom{k}{p}$