题目描述
有 $n$ 个整数变量，第 $i$ 个变量 $x_i$ 的取值范围是 $[0,A_i]$，设 $y_i=B_ix_i+C_i$
给定 $f(0),f(1), \cdots, f(k-1)$，保证 $f(0)=0$
对于所有变量 $x_i$ 的所有可能的取值情况，即一共 $\prod_{i=1}^{n}(A_i+1)$ 的取值情况
对于每种情况，求所有的 $y_i$ 在 $k$ 进制按位取最大值后得到的数字 $T=\sum t_ik^i$，然后求 $Q=\sum f(t_i)$
即假设 $y_i=\sum u_{i,j}k^j$，那么有 $t_j=\max_{i=1}^{n} u_{i,j}$
求所有方案的 $Q$ 的和，答案模 $998244353$
其中 $0\le A_i,B_i,C_i\le 10^9,1\le n\le 100,1\le k\le 1000,0\le f(i) < 998244353$
题解
显然要先拆位考虑，考虑枚举到位 $\omega$，之后对于每一个元素，只需要搞出这个东西就行了：
$$
f_{i,j}=\sum_{x=0}^{A_i} \left[\left\lfloor \frac{B_ix+C_i}{k^{\omega}} \right\rfloor \bmod k = j \right]
$$
然后就暴力跑一个 $\max$ 卷积就行了，也就是：
$$
c(k)=\sum_{\max(i,j)=k}a(i)b(j)
$$
求个前缀和就行了
那么就只剩下如何计算 $f_{i,j}$ 了
首先有：
$$
[a \bmod b=c]=[a \bmod b \le c]-[a \bmod b \le c-1]
$$
其次有：
$$
[a \bmod b \le c]= \left\lfloor \frac{a}{b} \right\rfloor - \left \lfloor \frac{a-c-1}{b} \right \rfloor
$$
同时有（实际上这个在这道题中没有用到）：
$$
\left\lceil \frac{a}{b} \right\rceil=\left\lfloor \frac{a+b-1}{b} \right\rfloor
$$
于是有：
$$
\begin{aligned}
f_{i,j}
=&\sum_{x=0}^{A_i} \left[\left\lfloor \frac{B_ix+C_i}{k^{\omega}} \right\rfloor \bmod k = j \right] \\
=&\sum_{x=0}^{A_i} \left[\left\lfloor \frac{B_ix+C_i}{k^{\omega}} \right\rfloor \bmod k \le j \right] - \left[\left\lfloor \frac{B_ix+C_i}{k^{\omega}} \right\rfloor \bmod k \le j-1 \right] \\
\end{aligned}
$$
把系数都合并出来，只需要实现函数 $g$，满足：
$$
g(a,b,c,n)=\sum_{i=0}^{n} \left\lfloor \frac{ai+b}{c} \right\rfloor
$$
那么 $f_{i,j}$ 可以变为：
$$
\begin{aligned}
f_{i,j}
=&\sum_{x=0}^{n} \left[\left\lfloor \frac{ax+b}{c} \right\rfloor \bmod d \le t\right] \\
=&\sum_{x=0}^{n} \left\lfloor \frac{ax+b}{cd} \right\rfloor-\left\lfloor \frac{\left\lfloor \frac{ax+b}{c}
\right\rfloor - (t + 1)}{d} \right\rfloor \\
=&g(a,b,cd,n)-\sum_{x=0}^{n} \left\lfloor \frac{ax+b-c(t+1)}{cd} \right\rfloor \\
=&g(a,b,cd,n)-g(a,b-c(t+1),cd,n)
\end{aligned}
$$
由于 $g(a,b,c,n)$ 中 $b$ 可能是负数，显然此时它应该等于：
$$
g(a,b,c,n)=g(a,b+\lambda c,c,n)-\lambda(n+1)
$$
此时有：
$$
\lambda=\left\lceil \frac{-b}{c} \right\rceil
$$
