好像虚高胡策搬过这道题

设\(t=\min a_i\)，不难发现我们一旦对\(t\)取模之后，就一定小于\(t\)，也就是之后再对其他数取模就没有什么意义了

当然一上来就可以对\(t\)取模，但是\(x\% t\)并不一定是最优答案，所以我们要通过其他的\(a_i\)把\(x\)调整一下，使得它模\(t\)的值尽量大

同时我们还发现多次对一个数取模是没有意义的，于是我们直接设\(f_i\)表示\(x\)是否能经过对\(a\)取模得到\(i\)这个数，每一次转移暴力把\(a\)扫一遍即可，可能这样一个数被多次使用，但是这并不会产生什么影响，不可能产生一个更优的答案，于是我们从小于\(t\)的\(i\)中找到一个\(f_i=1\)的最大的\(i\)即可，这就是第一问的答案了，复杂度是\(O(nx)\)

第二问计数，我记得胡策时大力写了一个爆搜发现能记忆化，就拿\(O(n^2x)\)搞了不少分

不过当时连为什么能记忆化都不太会

对于\(x\%a_i\)。如果\(a_i\leq x\)，那么\(x\%a_i\)后肯定会变小，定义这样的取模为有效取模；如果\(x>a_i\)，那么\(x=x\%a_i\)，定义这样的取模为无效取模

我们发现\(x\)对一个数取模之后很多\(a_i\)就都变成了无效取模，于是我们考虑只处理有效取模

我们把\(a\)从大到小排序，设\(dp_{x,l}\)表示当前的数为\(x\)，要处理的有效取模为\(l\)到\(n\)，答案就是\(dp_{x,1}\)

转移的话就是枚举接下来对哪一个数取模，对于新产生的无效取模，显然可以随便插到接下来的排列里

于是有

\[dp_{x,l}=\sum_{i=l}^ndp_{x\%a_i,id(x\%a_i)}A(n-id(x),id(x)-id(x\%a_i)-1)\]

其中\(id(x)\)就表示\(x\)对应的第一个有效取模，即排序之后第一个小于等于\(x\)的\(a\)的位置

对\(a_i\)取模之后要转移到的位置显然是\(id(x\%a_i)\)，中间空出来的无效取模就是从\(id(x)+1\)到\(id(x\%a_i)-1\)，这些无效取模就随便填到\(n-id(x)\)即还没有填的位置里去

发现这样做还是\(O(n^2x)\)的，但是很容易发现第二维没有什么用，因为\(x\)要处理的有效取模位置显然是\(id(x)\)，没有必要开第二维，于是复杂度就变成了\(O(nx)\)了

代码

#include 
    
     #define re register#define min(a, b) ((a) < (b) ? (a) : (b))const int mod = 998244353;const int maxn = 5e3 + 5;inline int read() {    char c = getchar();int x = 0;    while (c < '0' || c > '9') c = getchar();    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - 48, c = getchar();    return x;}inline int cmp(int A, int B) { return A > B; }int n, m, R, a[1005], inv[1005], fac[1005], id[maxn], ifac[1005];int f[maxn], dp[maxn], ans, vis[maxn];inline int A(int n, int m) {    if (m > n || m < 0) return 0;    return 1ll * fac[n] * ifac[n - m] % mod;}int dfs(int x) {    if (x < ans) return 0;    if (vis[x]) return dp[x];    vis[x] = 1;    for (re int i = id[x]; i <= n; i++)        dp[x] = (dp[x] + 1ll * dfs(x % a[i]) * A(n - id[x], id[x % a[i]] - id[x] - 1) % mod) % mod;    return dp[x];}int main() {    n = read();m = read();f[m] = 1;fac[0] = 1;inv[1] = 1;ifac[0] = 1;    for (re int i = 1; i <= n; i++) fac[i] = 1ll * i * fac[i - 1] % mod;    for (re int i = 2; i <= n; i++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;    for (re int i = 1; i <= n; i++) ifac[i] = 1ll * ifac[i - 1] * inv[i] % mod;    for (re int i = 1; i <= n; i++) a[i] = read();    R = a[1];for (re int i = 1; i <= n; i++) R = min(R, a[i]);    for (re int i = m; i >= 0; --i) {        if (!f[i]) continue;        for (re int j = 1; j <= n; ++j) f[i % a[j]] = 1;    }    for (re int i = R - 1; i >= 0; --i)        if (f[i]) {            id[i] = n + 1;;            printf("%d\n", ans = i);            break;        }    std::sort(a + 1, a + n + 1, cmp);    vis[ans] = dp[ans] = 1;    for (re int i = m;; --i) {        if (id[i]) break;        for (re int j = n; j; --j)            if (a[j] <= i) id[i] = j;            else break;    }    printf("%d\n", 1ll * dfs(m) * A(n, id[m] - 1) % mod);    return 0;}