「UOJ22」[UR#1]外星人

Description

2044年,Picks建成了人类第一台基于量子理论的银河系信息传递机。
Picks游遍了宇宙,雇用了 nn 个外星人来帮他作为信息传递机的中转站。我们将外星人依次编号为 11nn,其中 ii 号外星人有 aia_i 根手指。
外星人都是很低级的,于是Picks花费了很大的精力,才教会他们学会扳手指数数。
Picks现在准备传递 xx 个脉冲信号给VFleaKing,于是他把信号发给11号外星人,然后11号外星人把信号发送给22号外星人,22号外星人把信号发送给33号外星人,依次类推,最后nn号外星人把信号发给VFleaKing。
但是事情没有Picks想象的那么顺利,由于外星人手指个数有限,所以如果 ii 号外星人收到了 tt 个脉冲信号,他会错误的以为发送过来的是 tmodait \bmod a_i 个脉冲信号,导致只发送了 tmodait \bmod a_i 个脉冲信号出去。
Picks希望他发送出去的脉冲信号数量 xx 与VFleaKing收到的脉冲信号数量 yy 的差的绝对值尽量小。于是他决定通过重新排列这些外星人的顺序来达到这一目的。请你求出与 xx 之差最小的 yy。除此之外,请求出有多少种排列外星人的方式能达到最优解,你只需要输出方案数对 9982443539982443537×17×223+17 \times 17 \times 2^{23} + 1,一个质数)取模后的结果。

Input

第一行两个正整数n,xn, x
接下来一行有 nn 个正整数 aia_i,表示 ii 号外星人的手指数。

Output

第一行一个整数表示最优情况下VFleaKing收到的脉冲数量。
第二行一个整数表示达到最优情况的方案数。

Sample Input

1
2
2 15
7 10

Sample Output

1
2
5
1

explanation

共两种可行方案:
15mod7=115 \bmod 7 = 11mod10=11 \bmod 10 = 1
15mod10=515 \bmod 10 = 55mod7=55 \bmod 7 = 5
显然第二种方案更优。

HINT

n1000,x,ai5000n\leq1000,x,a_i\leq 5000

Solution

force

对答案有用的序列一定是递减的。
要么是不用,要么就是有用的序列之一。
fi+1f_{i+1}分别从fi,jf_{i,j}fi,j%aif_{i,j\% a_i}转移得到
不用的情况要特判i=ni=n的情况。共计4040分。

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<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const ll p = 998244353;
const int N = 1100;
int n, x;
ll cnt;
ll a[N];
bool cmp(int x, int y) {
return x > y;
}
bool f[2100][5100];
int main() {
n = read(), x = read();
for(int i = 1; i <= n; ++i) a[i] = read();
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 % a[i]] |= f[i - 1][j];
if(i < n)f[i][j] |= f[i - 1][j];
}
}
int ans = -1e9;
for(int i = 0; i <= x; ++i)
if(f[n][i] && abs(x - i) < abs(x - ans)) ans = i;
writeln(ans);
puts("0");
return 0;
}

std

考虑第ii个位置,要么aia_i有效,要么无效

  1. 无效,那么这个位置要给后面任意一个人,所以fi1,jfi,jf_{i-1,j}\to f_{i,j}
  2. 有效,那么就是fi1,jfi,jmodaif_{i-1,j}\to f_{i,j\bmod a_i}
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
46
47
48
49
50
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const ll p = 998244353;
const int N = 1100;
int n, x;
ll cnt;
ll a[N];
/*
f[i][j] //到i为止,值为j知否可行
a[i]>a[j]
*/
bool cmp(int x, int y) {
return x > y;
}
ll f[2100][5100];
int main() {
n = read(), x = read();
for(int i = 1; i <= n; ++i) a[i] = read();
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 % a[i]] += f[i - 1][j]) %= p;
if(i < n)f[i][j] += f[i - 1][j] * (n - i); //这个位置给后面任意一个人,有n-i可以放他
f[i][j] %= p;
}
}
int ans = -1e9;
for(int i = 0; i <= x; ++i)
if(f[n][i] && abs(x - i) < abs(x - ans)) ans = i;
writeln(ans);
writeln(f[n][ans]);
return 0;
}