問題一覧 > 通常問題

No.1697 Deque House

レベル : / 実行時間制限 : 1ケース 3.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 7
作問者 : eSeFeSeF / テスター : chineristACchineristAC 👑 ygussanyygussany
2 ProblemId : 6876 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-29 17:46:49

問題文

ある家では、$K$ 日間のパーティが行われる予定であり、$N$ 人の人が招待されています。 はじめ、$N$ 人の人は家の中で横一列に並んでいて、左から $i$ 番目 $(1\le i\le N)$ の人を人 $i$ と呼ぶことにします。

$K$ 日間のパーティについて、$d$ 日目 $(1\le d\le K)$ のパーティは以下のように行われる予定です。

  • $d$ 日目の時点で家に残っている人が、それぞれ独立に「帰る」「帰らない」の一方を選択する。
  • 「帰る」を選択した人のうち、以下のいずれかの条件を満たす人は家から退出する。それ以外の人はそのまま家に留まる。
    • 自分より右側に「帰らない」を選択した人が存在しない。
    • 自分より左側に「帰らない」を選択した人が存在しない。
  • この時点で、家に残っている人全員で $d$ 日目のパーティを行う。

なお、パーティのどの時点においても、家にいる人どうしの相対順序が変化することはありません

ところで、途中でパーティの参加者が1人ぼっちになってしまったり、 $K$ 日分の用意があるのに途中で全員帰ってしまうのは非常に悲しいことです。 そこで、$K$ 日間一連のパーティの成功度を、以下のように定めます。

  • $K$ 日間全てのパーティが2人以上で行われた場合
    • 人 $i$ が $K$ 日間でパーティに参加した日数を $D_i$ として、成功度は $\displaystyle\sum_{i=1}^{N}A_i^{D_i}$ とする。
  • $K$ 日間のうち1日以上で、パーティの参加人数が1人以下になってしまった場合
    • 成功度は、$0$ とする。

さて、$K$ 日間のパーティの行われ方は、各日における人の「帰る」「帰らない」の選択方法によって定まります。 そこで、考えうる全ての選択方法に対して、結果行われる $K$ 日間のパーティの成功度を計算しその合計を $998244353$ で割ったあまりを求めてください。

2つの選択方法が異なるとは、ある整数 $i$ および $d$ が存在して、$d$ 日目に人 $i$ が行った選択が異なることとします。

ここで、家から退出した人はそれ以降選択を行わないことに注意してください。

入力

$N\ \ K$
$A_1\ \ A_2\ \cdots \ A_N$
【制約】
  • $2\le N\le 10^5$
  • $1\le K\le 14$
  • $1\le A_i\lt 998244353$
  • 入力は全て整数

出力

答えを $\bmod{998244353}$ で出力せよ。

サンプル

サンプル1
入力
3 1
1 2 4
出力
25

1日だけパーティが開かれます。 「帰らない」を選択した人を 'o'、「帰る」を選択した人を 'x' で表せば、成功度が正になるような選択方法は以下です。

  • ooo
  • oox
  • oxo
  • xoo

それぞれ、家に留まる人は(人1、人2、人3)、(人1、人2)、(人1、人2、人3)、(人2、人3)であるので、 成功度の総和は $(1^1+2^1+4^1)+(1^1+2^1+4^0)+(1^1+2^1+4^1)+(1^0+2^1+4^1)=7+4+7+7=25$ です。

参加日数が0の人でも、成功度に影響する場合があることに注意してください。

サンプル2
入力
2 14
2997 92458
出力
660248434

最初から2人しか居ないため、2人が帰らずに2週間パーティをし続けた場合のみ成功度が正の値をとります。 この場合の成功度は $2997^{14}+92458^{14} \equiv 660248434\pmod{998244353}$ です。

サンプル3
入力
5 7
662 60 70 15 1034
出力
156455438

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