C. Permutation Partitions

Link

Solution

给定n、k和一个长度为n的排列，求该排列前k大数的和和将该排列分成k-1段且每段有且只有一个前k大数的分割方法数目

前k大数的和：(n*n+n-(n-k)*(n-k+1))/2

分割方法数目：设前k大数出现在数组中的位置分别为a1，a2，a3…ak，因为一段只能存在一个前k大数，所以从[0-a1]只有1种分法，(a1, a2]有(a2-a1)种分法，(a2, a3]有(a3-a2)种分法……以此类推，最终答案将这些分法乘起来即可。

Code

int main(int argc, char **argv) {
    LL n, k, tmp, ans = 1, pos = -1;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        if (tmp >= n - k + 1) {
            if (pos != -1)ans = 1LL * ans * (i - pos) % MOD;
            pos = i;
        }
    }
    cout << (n*n + n - (n - k) * (n - k + 1)) / 2 << " " << ans << endl;
    return 0;
}