#P18524. Shell Sort
Shell Sort
Shell Sort
希尔排序是一种分组插入排序。给长度为 的序列 升序排序时,先选定正整数 ,以及长度为 、严格递减且最后一个数为1的步长序列 ,然后执行 轮操作。
第 轮令 ,把所有位置按其下标模 的余数分为 组,分别在每组内进行插入排序,再写回原位置。原题具体算法如下;swap_count 每次只因一次组内相邻元素的交换而增加1,而非按这两个元素在原数组中的下标距离增加。
void insert_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]);
insert_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();
}
}
给定 ,对 的所有排列分别运行上述算法,求 swap_count 的最大值,以及有多少个排列达到这个最大值。两个答案均对 取模。
输入格式
第一行两个整数 (,)。
第二行 个整数 ,保证 、,且对每个 ,均有 。
只有一组输入。允许某个步长不小于 ,这轮各组至多一个元素,不产生交换。
输出格式
一行两个整数,依次表示最大交换次数和达到该次数的排列数;二者均对 取模。
原样例
输入:
5 2
2 1
输出:
7 2