問題一覧 > 通常問題

No.2058 Binary String

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 93
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : nok0nok0 👑 ygussanyygussany
4 ProblemId : 8334 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-15 00:30:48

問題文

正整数 $N,K$ が与えられます。 長さ $N$ の数列のうち次の条件を満たすものを良い数列と呼ぶことにします。

  • $1 \le i \le N $ を満たす全ての整数 $i$ に対して $ S_i \in \lbrace 0,1 \rbrace$
  • $\displaystyle \sum_{i=1}^N S_i \equiv 0 \ (\mathrm{mod}\ 2)$

また良い数列 $S$ に対して次の操作を $0$ 回以上行なって $S$ の要素を全て $0$ にするための最小操作回数を $f(S)$ とします。（$S$ が良い数列ならば $f(S)$ は有限の値になります。）

  • $1 \le i \le N-1$ を満たす整数 $i$ を一つ選び $S_i$ を $1-S_i$ に、$S_{i+1}$ を $1-S_{i+1}$ に置き換える

良い数列 $S$ は $2^{N-1}$ 個ありますが、その全てに対して $f(S)$$^K$ を求め、その総和を $998244353$ で割った余りを求めてください。

入力

$N$ $K$

  • $2 \le N \le 2×10^5$
  • $1 \le K \le 2×10^5$
  • 入力は全て整数

    • 出力

    $f(S)^K$ の総和を $998244353$ で割った余りを出力してください。

    サンプル

    サンプル1
    入力
    3 2
    出力
    6

    $f((0,0,0))=0、f((1,1,0))=f((0,1,1))=1、f((1,0,1))=2$です。よって答えは $1^2+1^2+2^2=6$ となります。

    サンプル2
    入力
    10 3
    出力
    62208

    サンプル3
    入力
    200000 2
    出力
    829773566

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。