dp+计数

题意是让我们求$val \space mod \space a_1 \space mod \space a_2 \space mod \space ... \space mod \space a_n$的最大值

我们发现如果对于任意的 $i < j$ ，满足 $a_i < a_j$ ，那么j这个位置就是无用的，我们可以直接忽略掉他

显然a数组的顺序不影响结果，所以先对a数据从大到小排序

所以我们用$f_{i,j}$表示前i大的选出几个取模后能否使结果为j，能为1，不能则为0

状态转移方程为$f_{i,j}|=f_{i-1,j+a_i*k} \space k \in N^*$

边界为$f_{i,m \space mod \space a_i}=1$

第一问的答案就是使得$f_{n,i}$为1的i中的最大值

第二问是个计数

我们用$g_{i,j}$表示前i大的选出几个取模后能否使结果为j的方案数

显然出状态为$g_{0,ans}=1$

状态转移为$g_{i,j}=g_{i-1,j}*(i-1)+g_{i-1,j \space mod \space a_{n-i+1}}$

方案数的转移解释一下，这里从小往大算。 - 如果这个在中间任意一个位置加，不影响当前答案，有$g_{i-1,j}*(i-1)$种方案 - 如果加在最前面，就是取模之后再算

最后的答案是$g_{n,m}$

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1010,M=5010,mod=998244353;
ll n,m,a[N],f[N][M],g[N][M],ans;

inline ll read(){
    ll x=0,tmp=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') tmp=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return tmp*x;
}

inline bool cmp(ll x,ll y){
    return x>y;
}

int main(){
    n=read(); m=read();
    for(ll i=1; i<=n; i++) a[i]=read();
    sort(a+1,a+1+n,cmp);
    for(ll i=1; i<=n; i++){
        f[i][m%a[i]]=1;
        for(ll j=0; j<a[i]; j++){
            for(ll k=j; k<=m; k+=a[i]) f[i][j]|=f[i-1][k];
        }
    }
    for(ll i=a[n]-1; i>=0; i--){
        if(f[n][i]){
            ans=i;
            break;
        }
    }
    cout<<ans<<endl;
    g[0][ans]=1;
    for(ll i=1; i<=n; i++){
        for(ll j=0; j<=m; j++) g[i][j]=(g[i-1][j]*(i-1)+g[i-1][j%a[n-i+1]])%mod;
    }
    cout<<g[n][m]<<endl;
    return 0;
}