题解：
质量不错的一套题目啊。。（题解也很不错啊）
t1:
首先暴力显然有20分，把ai相同的缩在一起就有40分了
然后会发现由于原来的式子有个%很不方便处理
so计数题嘛 考虑一下容斥
最终步数=初始步数-使用tab键减少的步数=(x-1)*sigma(ai/x)
这个显然就很好维护了
我们考虑对于ai/x只会有根号ai个取值
然后每个值分别实现区间加区间减 这样用差分来做就是n根号x 线段树nlogn根号x
复杂度稍微大了点
满分做法就是枚举x，然后枚举y，计算a[i]/x=y的数有几个，计算用前缀和处理一下
复杂度的话是n/1+n/2+n/3+...=nlogn的
t2:
感觉跟zjoi的dp挺像的。。（虽然简单一点）
首先要先弄出一波结论
就是若我们使用了ai，且ai<aj，那么再使用j就没有任何影响了
所以我们可以先将元素降序排列
令f[i][j]表示前i个,%的值为j是否可行
转移就是从f[i][j]------->f[i+1][j%a[i+1]]
这样第一问就解决了
对于第二问
首先排序是一样的
我们可以令f[j][k] 表示 当前%的值为j，其中有k个值比j大且还没有放（比j小的是一定还没放的）
那么转移就是f[j][k]--->f[j%a[now]][k+sum[now]-sum[j]] (now代表比j小的元素）
或者f[j][k]--->f[j][k-1]
这样复杂度是n^3的
考虑优化状态
令f[i]表示当前%的值为i的方案数
那么考虑转移 f[i]---->f[j] 我们会发现，对于i-j之间的元素(设有y个），只有插入在这个点之后就行了，设x=比j小的元素个数
其实就是x+1个空里插y个数
那就是乘以A(y-1，x+y）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mo1=;
#define N 11100
ll jc1[N*],jc2[N*],n,m,a[N],f[][N],dp[N];
ll sum[N];
ll x,y,ans;
bool cmp(ll x,ll y)
{
return(x>y);
}
ll get_gcd(ll a,ll b,ll &x,ll &y)
{
// cout<<a<<" "<<b<<endl;
if (b==)
{
x=; y=; return(b);
}
ll xx=get_gcd(b,a%b,y,x);
y-=x*(a/b);
return xx;
}
ll get_ans(ll x,ll y)
{
// cout<<x<<" "<<y<<endl;
if (y==) return();
ll ans=(jc1[x+y-]*jc2[x-])%mo1;
// cout<<jc1[x+y-1]<<" "<<jc2[x-1]<<" "<<ans<<endl;
return ans;
}
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
std::ios::sync_with_stdio(false);
cin>>n>>m;
for (ll i=;i<=n;i++)
cin>>a[i];
sort(a+,a+n+,cmp);
f[][m]=;
for (ll i=;i<=n-;i++)
{
for (ll j=;j<=m;j++)
if (f[i][j])
f[i+][j%a[i]]=,f[i+][j]=;
}
for (ll j=;j<=m;j++)
if (f[n][j])
f[n+][j%a[n]]=;
ll j;
for (j=m;j>-;j--)
if (f[n+][j]) break;
ans=j; cout<<ans<<endl;
jc1[]=jc2[]=jc1[]=jc2[]=;
for (ll i=;i<=;i++)
{
get_gcd(mo1,i,x,y);
x=(x+mo1)%mo1;
jc1[i]=jc1[i-]*i;
jc1[i]%=mo1;
jc2[i]=jc2[i-]*y;
jc2[i]%=mo1;
}
dp[m]=;
for (ll i=;i<=n;i++) sum[a[i]]++;
for (ll i=;i<=;i++) sum[i]+=sum[i-];
ll num=;
for (ll i=;i<=n;i++) if (a[i]>m) num++;
for (ll i=m;i>=ans;i--)
if (dp[i])
{
ll j;
for (j=;j<=n;j++)
if (a[j]<=i) break;
x=j;
for (ll j=x;j<=n;j++)
{
dp[i%a[j]]+=dp[i]*get_ans(sum[i%a[j]]+,sum[i]--sum[i%a[j]]);
get_ans(n-j+,j-x);
dp[i%a[j]]%=mo1;
}
}
ll ans1=dp[ans];
// cout<<ans1<<"XXX"<<endl;
ans1=ans1*get_ans(n-num+,num);
ans1%=mo1;
cout<<(ans1+mo1)%mo1<<endl;
return ;
}