# ARC114-C Sequence Scores

2056diff
https://atcoder.jp/contests/arc114/tasks/arc114_c

## 解法

$f(A)$の計算方法を考える。

1. $X_{i}\lt A_{i}$なる$i$の中で最小のものを取り、これを$l$とする。
2. $l\le j\land X_{j} = A_{j}$なる$j$の中で最小のものを取り、これを$r$とする。存在しない場合は$r = N + 1$とする。
3. $X_{l}, X_{l + 1}, \dots, X_{r - 1}$を$\min_{i = l}^{r - 1} A_{i}$で置き換える

この手法を$X \ne A$の間繰り返すことで、最小操作回数で達成できる。

この操作回数は$f(A) = N - |\{\ i\ |\ \exists j\ j\lt i\land A_{j} = A_{i}\land A_{i}\lt \min_{k = j + 1}^{i - 1} A_{k}\}|$である

主客転倒を考える。$i = 1, 2, \dots, M$それぞれについて$i$が$f(A)$式内の集合に含まれるような$A$の数$C_{i}$をそれぞれ数え上げ、$NM^{N}$からその総和を引くことで解を求める。

$j$の位置および$A_{i}$を固定することを考えると、その数は$B_{i} = \sum_{j = 1}^{i - 1} (M^{j - 1 + N - i})\sum_{k = 1}^{M} (M - k)^{i - j - 1}$

である。これを愚直に計算すると3乗かかるが、$\sum_{k = 1}^{M} (M - k)^{i - j - 1}$は前計算できる。

以上より、$O(N(M + N))$で解けた。

## 実装

#include <bits/stdc++.h>

const long long MOD{998244353};

long long add(long long a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
}

long long minus(long long v) {
    return v ? MOD - v : v;
}

long long mult(long long a, long long b) {
    return (a * b) % MOD;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N, M;
    std::cin >> N >> M;
    std::vector pow(M + 1, std::vector(N + 1, 1));
    for (int i{} ; i <= M ; i++) for (int j{1} ; j <= N ; j++) {
        pow[i][j] = mult(pow[i][j - 1], i);
    }
    std::vector<long long> sum(N + 1);
    for (int i{} ; i <= N ; i++) {
        for (int j{} ; j < M ; j++) {
            sum[i] = add(sum[i], pow[j][i]);
        }
    }
    long long ans{mult(N, pow[M][N])};
    for (int i{2} ; i <= N ; i++) {
        for (int k{i - 1} ; k >= 1 ; k--) {
            int len{i - k - 1};
            // long long val{};
            // for (int j{1} ; j <= M ; j++) {
            //     val = add(val, pow[M - j][len]);
            // }
            // std::cout << val << ' ' << val2 << std::endl;
            long long val{mult(sum[len], pow[M][k - 1 + N - i])};
            ans = add(ans, minus(val));
        }
    }
    std::cout << ans << '\n';
}

[提出](https://atcoder.jp/contests/arc114/submissions/58147790)

## 感想

典型っぽい見た目でやりやすそうだと考察入れ始めてから、大変時間がかかってしまった。

始めはDPで解けないか考えていて、主客転倒に方針を変えるまでに一日以上かかってしまった。

$f(A)$の計算式も正しいものを手に入れるまで何回か間違った計算式で考察を入れてしまった。