【UOJ#22】【UR #1】外星人（动态规划）

题面

题解

一道简单题？

不难发现只有按照从大往小排序的顺序选择的才有意义，否则先选择一个小数再去模一个大数是没有意义的。

设\(f[i][j]\)表示考虑了前\(i\)个数，模完之后是\(j\)的方案数。

转移的时候枚举这个数是模还是不模，如果不模的话就要把它放到后面某个小数的后面，方案数是\(n-i\)。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAX 5050

#define MOD 998244353

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

inline int read()

{

    int x=0;bool t=true;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=false,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return t?x:-x;

}

int n,x,a[MAX],f[MAX][MAX];

int main()

{

	n=read();x=read();

	for(int i=1;i<=n;++i)a[i]=read();

	sort(&a[1],&a[n+1]);reverse(&a[1],&a[n+1]);

	f[0][x]=1;

	for(int i=1;i<=n;++i)

	{

		for(int j=0;j<=x;++j)add(f[i][j],1ll*f[i-1][j]*(n-i)%MOD);

		for(int j=0;j<=x;++j)add(f[i][j%a[i]],f[i-1][j]);

	}

	for(int i=x;~i;--i)if(f[n][i]){printf("%d\n%d\n",i,f[n][i]);return 0;}

	return 0;

}

巴特西

【UOJ#22】【UR #1】外星人（动态规划）

【UOJ#22】【UR #1】外星人（动态规划）

题面

题解

最新文章

热门文章