希尔排序是一种优秀的排序算法,可以看做是一种分组插入排序,接下来我们简单介绍一下该算法:
假设现在需要对一个长度为 n 的序列 A0…n−1 进行升序排序,首先我们需要确定一个整数 m 和一个长度为 m 递减且最后一个数为 1 的序列 d 作为步长序列,然后进行 m 轮操作。
对于第 i 轮操作,令 t=di,然后考虑把 A 分成尽量均匀的 t 组,具体的,我们选择把下标对 t 取模相同的那些位置分到一组,然后对每个组内的数去做插入排序。
具体的,可以参照以下 C++ 代码:
void bubble_sort(vector<int> &v) {
int n = v.size();
for (int i = 0; i < n; i++) {
for (int j = i; j && v[j] < v[j - 1]; j--){
swap(v[j], v[j - 1]);
swap_count++;
}
}
}
void work() {
for (int i = 0; i < t; i++) {
vector<int> v;
for (int j = i; j < n; j += t) v.push_back(A[j]);
bubble_sort(v);
for (int j = i, k = 0; j < n; j += t, k++) A[j] = v[k];
}
}
void shell_sort() {
swap_count = 0;
for (int i = 1; i <= m; i++) {
t = d[i];
work();
}
}
其中的 work
函数就表示了一轮参数为 t=d[i] 的操作。
现给定两个整数 n,m, 以及一个长度为 m 的步长序列 d,你需要计算对于所有长度 1∼n 的排列,在运行 shell_sort
函数后,数组元素交换次数,也就是变量 swap_count
的最大值。同时,你需要给出有多少个排列,能够达到这个最大值。
答案均需对 109+7 取模。
输入格式
第一行两个整数 n,m。
第二行 m 个整数,第 i 个表示 di。
输出格式
一行两个整数,分别表示最多次数和达到最多次数的排列数量。答案均需对 109+7 取模。
样例数据
样例输入
5 2
2 1
样例输出
7 2
样例解释
两个排列分别是 [3,5,2,4,1] 和 [5,2,4,1,3]。
子任务
对于全部的数据,满足 2≤n≤30,1≤m≤10,d1≤10,dm=1 且 ∀i=1,2,…,n−1 均有 di<di+1
- Subtask1(18pts):n≤8。
- Subtask2(27pts):n≤16。
- Subtask3(21pts):n≤22。
- Subtask4(10pts):m=2。
- Subtask5(24pts):无特殊限制。