はまやんはまやんはまやん

hamayanhamayan's blog

Permutation Partitions [Codeforces Global Round 7 C]

https://codeforces.com/contest/1326/problem/C

解説

https://codeforces.com/contest/1326/submission/73896496

最善の答えは、最も大きいK個の総和であり、これはうまく分割することで達成できる。
そのような分割にするには、最も大きいK個の間に分割の仕切り棒を入れればいい。
もう一つの答えはその仕切り棒の組み合わせである。
最も大きいK個がある座標をidx[0], idx[1], ..., idx[K-1]とすると、
idx[0]とidx[1]の間の仕切り棒の置き方の組み合わせはidx[1]-idx[0]となる。
他も同様に差が仕切り棒の置き方の組み合わせである。
これらの総積が組み合わせ数となる。

int N, K, P[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> P[i];

    vector<int> idx;
    rep(i, 0, N) if (N - K < P[i]) idx.push_back(i);

    ll ans1 = 0;
    rep(k, 0, K) ans1 += N - k;

    mint ans2 = 1;
    rep(k, 0, K - 1) ans2 *= idx[k + 1] - idx[k];
    cout << ans1 << " " << ans2 << endl;
}