[DP] UOJ22. [UR #1] 外星人

不难的 \(DP\)

首先想到真正使 \(x\) 变小的一定是递减的一些数,若当前 \(a_i>x\) ,则之后 \(a_i\) 就可以随便放。

所以第一问就很简单了,就是取一些下降的数,最小的 \(a_i\) 必取的, \(xjb\) \(DP\) 一下。

考虑第二问,肯定还是 \(DP\) 。思考一下,发现只需记一维:

\(f(i)\) 表示当前 \(x=i\), 只考虑不大于 \(i\) 的数,最后模到 \(ans1\) 的方案数。

撕烤一下转移,大概是 \(f(i) \leftarrow cnt_j\ f(i\text{ % } j)\ w(i,j)\)

其中 \(w(i,j)\) 表示那些剩下的大于 \(i\text{ % }j\) 的数随便插到后面。

这样就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=5005,P=998244353;
int n,K,a[maxn],cnt[maxn],sum[maxn],ans1,ans2;
LL f[maxn],fac[maxn],inv[maxn],fac_inv[maxn];
bool g[maxn];
int get(int n,int m){
return fac[n+m]*fac_inv[m]%P;
}
int main(){
freopen("uoj22.in","r",stdin);
freopen("uoj22.out","w",stdout);
scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++) scanf("%d",&a[i]), cnt[a[i]]++;
sum[0]=cnt[0]; for(int i=1;i<=5000;i++) sum[i]=sum[i-1]+cnt[i];
sort(a+1,a+1+n);
g[K]=1;
for(int i=n;i>=2;i--)
for(int j=0;j<=K;j++) g[j%a[i]]|=g[j];
for(int i=0;i<=K;i++) if(g[i]) ans1=max(ans1,i%a[1]);
printf("%d\n",ans1);
fac[0]=1; for(int i=1;i<=5002;i++) fac[i]=fac[i-1]*i%P;
inv[1]=1; for(int i=2;i<=5002;i++) inv[i]=(LL)(P-P/i)*inv[P%i]%P;
fac_inv[0]=1; for(int i=1;i<=5002;i++) fac_inv[i]=fac_inv[i-1]*inv[i]%P;
f[ans1]=1;
for(int i=1;i<=K;i++)
for(int j=1;j<=i;j++)
f[i]=(f[i]+f[i%j]*get(sum[i]-sum[i%j]-1,sum[i%j])%P*cnt[j]%P)%P;
printf("%d\n",f[K]*get(sum[5000]-sum[K],sum[K])%P);
return 0;
}