pythonで青くなるブログ

主に競プロのについての記事(日記的な)を書きます。現在atcoder水色,こどふぉ青色。python3使って、やってます。atcoder青くなりたい

Educational Codeforces Round 83 D

atcoder python 競プロ

内容

  • EC R-83 D問題　Count the Arraysをpythonでと解きました。

問題

codeforces.com

以下の条件を満たす配列 A の数を求める

  • len(A)=N
  • Aの要素は [1,M]
  • ちょうど一つ、等しい数のペアを含む
  • あるインデックス　iが存在し、1~iまでは単調増加、i~Nまでは単調減少となる

入力

  • N:配列の長さ
  • M:配列の数字の上限

出力

  • 条件を満たす配列の数を、mod 998244353 したもの

ポイント

  1. Aに含まれる数字の選び方 : MC(N-1)

    • Aには、N-1個の独立した要素が含まれる。
      • ちょうどひとつ、等しい数字のペアがあるから。
  2. 2回現れる数字の選び方 :(N-2)通り
    • 2回現れる数字はMではない。
      • 最大の数が2回現れると、単調増加・減少の条件を見たせない。
  3. 並び方: 2N-3通り
    • 選んだ数字を、折り返し地点iより右か左かに分ける(2回現れる数字以外でN-3個)
      • 2回現れる数字は、左右に一つずつ。
      • 左側は昇順、右側は降順に並ぶため、並べ方は一通りに決まる 　　　

よって、MC(N-1)(N-3)nN-3のmodを取ったものが答えとなる。 (注)N=2のときは、2N-3の計算が辛いので、別途処理する。

実装

# -*- coding: utf-8 -*-


class FactMod():
    #よく使う逆元のやつ
    def __init__(self, n, mod):
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def comb(self, n, r):
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


N, M = map(int, input().split())

MOD = 998244353
F = FactMod(M, MOD)

if N == 2:
    print(0)
else:
    ans = F.comb(M, N-1)*(N-2)*pow(2, N-3, MOD) % MOD
    print(ans)

終わりに

  • 解説AC

最近買ったもの

  • モニターがある生活は強い。