問題一覧 > 通常問題

No.2005 Sum of Power Sums

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : to-omerto-omer / テスター : chineristACchineristAC 👑 ygussanyygussany
3 ProblemId : 7718 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-07-05 22:14:53

問題文

長さ $N$ の非負整数列 $A$ であって $\displaystyle \sum_{i=1}^{N}A_i\le M$ を満たすものすべてに対して、 $\displaystyle \sum_{i=1}^{N}A_i^{K_i}$ の和をとったものを $998244353$ で割った余りを求めてください。

制約

  • 入力は全て整数である。
  • $1\le N\le 2\times 10^5$
  • $1\le M\le 10^{18}$
  • $1\le K_i\le 5000\ (1\le i\le N)$

入力

$N$ $M$
$K_1$ $K_2$ $\dots$ $K_N$

出力

答えとなる整数を 1 行で出力してください。

サンプル

サンプル1
入力
2 2
1 2
出力
10
  • $A=(0,\ 0)$ のとき $0^1+0^2=0$
  • $A=(0,\ 1)$ のとき $0^1+1^2=1$
  • $A=(0,\ 2)$ のとき $0^1+2^2=4$
  • $A=(1,\ 0)$ のとき $1^1+0^2=1$
  • $A=(1,\ 1)$ のとき $1^1+1^2=2$
  • $A=(2,\ 0)$ のとき $2^1+0^2=2$

よって、答えは $0+1+4+1+2+2=10$ です。

サンプル2
入力
1 10
4
出力
25333
サンプル3
入力
3 14159265
3589 793 2384
出力
90586659

$998244353$ で割った余りを求めてください。

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