問題一覧 > 通常問題

No.2484 Add to Variables

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 38
作問者 : MagentorMagentor / テスター : ytqm3ytqm3
3 ProblemId : 10103 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-22 22:18:52
F 問題と G 問題は設定が共通しており、制約のみが異なります。

問題文

ここに、長さ $N$ の数列 $A$ があります。最初、 $A$ のすべての値は $0$ です。

この数列に対し、以下の $4$ 種類の操作を行うことを考えます。

  • 何もしない。
  • 整数 $k \ (1 \leq k \leq N-1)$ を選び、$1 \leq i \leq k$ を満たす全ての整数 $i$ について、 $A_i$ に $1$ を足す。
  • 整数 $k \ (2 \leq k \leq N)$ を選び、$k \leq i \leq N$ を満たす全ての整数 $i$ について、 $A_i$ に $1$ を足す。
  • $1 \leq i \leq N$ を満たすすべての整数 $i$ について、 $A_i$ に $1$ を足す。

操作をちょうど $M$ 回行う方法のうち、 $A=B$ となるものの個数を $998244353$ で割った余りを求めてください。

ただし、ある整数 $i$ が存在して $i$ 回目に $1$ が足された数の index の集合が異なる時、またその時に限り操作列が異なるとみなします。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$
$B_1$ $B_2$ $\ldots$ $B_N$
  • 入力は全て整数
  • $N=4$
  • $1 \le M \le 2 \times 10^5$
  • $0 \leq B_i \leq M$

出力

答えを出力せよ。

サンプル

サンプル1
入力
4 2
1 1 1 0
出力
2

$1$ 回目の操作で $A_1,A_2,A_3$ に $1$ を足し、$2$ 回目の操作でどの変数にも $1$ を足さない方法と、$1$ 回目の操作でどの変数にも $1$ を足さず $2$ 回目の操作で $A_1,A_2,A_3$ に $1$ を足す方法の $2$ 通りが考えられます。

サンプル2
入力
4 2
1 1 1 1
出力
8
$1$ 回目の操作で $1$ が足されなかった変数に $1$ を足したときに限り $A_1=A_2=A_3=A_4=1$ を達成することが出来るので、答えは $8$ 通りです。
サンプル3
入力
4 3
0 3 2 2
出力
0
サンプル4
入力
4 314
202 3 9 22
出力
362672301

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