【UR #1】外星人(dp思维技巧)
- 考虑去除后效性，常用方法排序
- 状态可以直接以答案为状态来判断合法性
- 考虑转移方向，向后转移，选与不选来定向答案
f[i][j]表示前i个数答案为j的方案数
不选i 则加上f[i][j] 的方案数 * （n-i）,ai可以在后面随便选。
选i 则加上f[i][j] 的方案数，ai定在了i这个位置。
【UR #1】外星人 - 题目 - Universal Online Judge
AC 代码
#include<bits/stdc++.h>
using namespace std;
long long f[5050][5050];
int a[5050];
int x;
int n;
int mod = 998244353;
bool cmp(int a,int b){return a>b;
}
int main(){cin>>n;cin>>x;for(int i = 1;i <= n;i++)cin>>a[i];sort(a+1,a+1+n,cmp);f[0][x] = 1; for(int i = 1;i <= n;i++){for(int j = 0;j <= x;j++){f[i][j] += f[i-1][j]*(n-i);f[i][j]%=mod;}for(int j = 0;j <= x;j++){f[i][j%a[i]] += f[i-1][j];f[i][j%a[i]]%=mod;}}for(int i = x;i >= 0;i--){if(f[n][i]){cout<<i<<endl;cout<<f[n][i]<<endl;return 0;}}return 0;
}