xht37 的洛谷博客

xht37's blog:https://www.xht37.com/

题解 CF1326C 【Permutation Partitions】

最大值肯定可以选择 $n,n-1,\cdots,n-k+1$ 这 $k$ 个数相加。

求方案数时,相邻两个区间的间隔一定在两个选择的数中间,因此将位置之差相乘即可。

时间复杂度 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, k;
ll a[N], ans;
modint Ans = 1;

int main() {
    rd(n), rd(k), rda(a, n);
    for (int i = 1; i <= k; i++) ans += n + 1 - i;
    print(ans, ' ');
    vi p;
    for (int i = 1; i <= n; i++)
        if (a[i] > n - k) p.pb(i);
    for (ui i = 1; i < p.size(); i++)
        Ans *= p[i] - p[i-1];
    print(Ans);
    return 0;
}

2020-03-21 04:40:48 in 题解