Uoj 22 外星人
- 注意到一个数只有 \(\%\) 了小于等于自己的数时,才可能有变化,否则可以随意安排,不会对最后最优解造成影响.
- 用 \(f[x]\) 表示给一个数 \(x\) ,仅用 \(a[i]<=x\) 的 \(a[i]\) 时,得到的最大数.用 \(g[x]\) 表示最优情况下的方案数目.
- 转移时,对于会造成影响的数,我们枚举第一个位置填的数,对于不会造成影响的数,就任意给它们钦定位置.
- 记 \(p=x\ mod\ a[i]\) ,\(count_k\) 表示小于等于 \(k\) 的 \(a[i]\) 个数,容易写出转移方程:
\[f[x]=\max_{a[i] \leq x} (f[x],f[p])\\
g[x]=\sum_{a[i]\leq x\ ,\ f[p]=f[x]}g[p]*A(count_x-1,count_p-1)
\]
g[x]=\sum_{a[i]\leq x\ ,\ f[p]=f[x]}g[p]*A(count_x-1,count_p-1)
\]
- 边界条件:
\[f[x]=x,count_x=0\\
g[x]=1,count_x=0
\]
g[x]=1,count_x=0
\]
- 最后输出答案的时候还要注意大于给出 \(x\) 的数可以任意放.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
fh=-1,jp=getchar();
while (jp>='0'&&jp<='9')
out=out*10+jp-'0',jp=getchar();
return out*fh;
}
const int P=998244353;
inline int add(int a,int b)
{
return (a + b) % P;
}
inline int mul(int a,int b)
{
return 1LL * a * b % P;
}
int fpow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
res=mul(res,a);
a=mul(a,a);
b>>=1;
}
return res;
}
const int MAXN=1e3+10,MAXV=5e3+10;
int n,X;
int a[MAXN],f[MAXV],g[MAXV];
int fac[MAXV],invfac[MAXV];
void init()
{
int lim=5000;
fac[0]=1;
for(int i=1;i<=lim;++i)
fac[i]=mul(fac[i-1],i);
invfac[lim]=fpow(fac[lim],P-2);
for(int i=lim-1;i>=0;--i)
invfac[i]=mul(invfac[i+1],i+1);
}
int A(int n,int m)
{
if(m<0 || n<0 || m>n)
return 0;
return mul(fac[n],invfac[n-m]);
}
int count(int L,int R)//计算a数组从L到R有多少个数
{
if(L>R)
return 0;
int l=lower_bound(a+1,a+1+n,L)-a;
int r=upper_bound(a+1,a+1+n,R)-a-1;
return r-l+1;
}
int dfs(int x)
{
if(f[x]!=-1)
return f[x];
f[x]=-1,g[x]=0;
int k=count(1,x);
if(k==0)
{
f[x]=x;
g[x]=1;
return x;
}
for(int i=1;i<=n;++i)
{
if(a[i]<=x)
{
int p=x%a[i];
f[x]=max(f[x],dfs(p));
}
else
break;
}
for(int i=1;i<=n;++i)
{
if(a[i]>x)
break;
int p=x%a[i];
if(f[p]!=f[x])
continue;
int tmp=g[p];
int tot=count(1,x)-1,par=count(p+1,x)-1;
tmp=mul(tmp,A(tot,par));
g[x]=add(g[x],tmp);
}
return f[x];
}
int main()
{
init();
n=read(),X=read();
memset(f,-1,sizeof f);
for(int i=1;i<=n;++i)
a[i]=read();
sort(a+1,a+1+n);
dfs(X);
int t=count(X+1,a[n]);
printf("%d\n%d\n",f[X],mul(g[X],A(n,t)));
return 0;
}