1 of 7

C: Magnet

全体FA: ajaja_hint_azamasu (08:04)�オンサイトFA: touhokudai (17:04)

AC: 21/35

原案: amesyu

​

2 of 7

問題概要

\sum_{i=1}^{N-1} max(A_{P_{i}}, A_{P_{i + 1}}) が最小となる順列Pの個数を998244353で割ったあまりを求めよ。

  • 2 ≤ N ≤ 2×105
  • 0 ≤ Ai ≤ 109

3 of 7

解法

Aを並び替えたもので、とあるiが存在して、

iより左側が広義単調減少�iより右側が広義単調増加

となっていればよい。

4 of 7

具体的に

Aiは高々隣接の2回分しか寄与できないのでAiを1回ずつ寄与させるような並べ替えがしたい。

ある値が2回寄与する時、その値より小さいものが寄与していないことになり、これは損。

両隣にその値より真に小さい値を置くとその値が2回寄与。

例:

6

1

7

4

6

7

7

5 of 7

数え上げpart

最小値がk個ある時、最小値の並び替えはk!通り。

それ以外の値は小さい順に、右または左に配置することを考えると同じ値がk個ある時、それより小さい値のかたまりを仕切りとして考えると (k+1)!になる！

​

6 of 7

例 (N = 6, A = [1, 4, 1, 4, 2, 1])

1の並び替えは3!通り

2未満と2の並び替えは2!

4未満と4の並び替えは3!

答えは 3! × 2! × 3! = 72

1

1

1

2

1,1,1

1,1,1,2

4

4

7 of 7

計算量

値の個数が必要なのでmap, unordered_mapなどを用いてO(NlogN), O(N)で解くことができた。