#P18524. Shell Sort

Shell Sort

Shell Sort

希尔排序是一种分组插入排序。给长度为 nn 的序列 A0,A1,…,An−1A_0,A_1,\ldots,A_{n-1} 升序排序时,先选定正整数 mm,以及长度为 mm、严格递减且最后一个数为1的步长序列 dd,然后执行 mm 轮操作。

第 ii 轮令 t=dit=d_i,把所有位置按其下标模 tt 的余数分为 tt 组,分别在每组内进行插入排序,再写回原位置。原题具体算法如下;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();
    }
}

给定 n,m,dn,m,d,对 1,2,…,n1,2,\ldots,n 的所有排列分别运行上述算法,求 swap_count 的最大值,以及有多少个排列达到这个最大值。两个答案均对 109+710^9+7 取模。

输入格式

第一行两个整数 n,mn,m(2≤n≤302\le n\le30,1≤m≤101\le m\le10)。

第二行 mm 个整数 d1,d2,…,dmd_1,d_2,\ldots,d_m,保证 1≤di≤101\le d_i\le10、dm=1d_m=1,且对每个 1≤i<m1\le i<m,均有 di>di+1d_i>d_{i+1}。

只有一组输入。允许某个步长不小于 nn,这轮各组至多一个元素,不产生交换。

输出格式

一行两个整数,依次表示最大交换次数和达到该次数的排列数;二者均对 109+710^9+7 取模。

原样例

输入:

5 2
2 1

输出:

7 2