問題一覧 > 通常問題

No.2005 Sum of Power Sums

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

問題文

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

制約

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

入力

NN MM
K1K_1 K2K_2 …\dots KNK_N

出力

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

サンプル

サンプル1
入力
2 2
1 2
出力
10
  • A=(0, 0)A=(0,\ 0) のとき 01+02=00^1+0^2=0
  • A=(0, 1)A=(0,\ 1) のとき 01+12=10^1+1^2=1
  • A=(0, 2)A=(0,\ 2) のとき 01+22=40^1+2^2=4
  • A=(1, 0)A=(1,\ 0) のとき 11+02=11^1+0^2=1
  • A=(1, 1)A=(1,\ 1) のとき 11+12=21^1+1^2=2
  • A=(2, 0)A=(2,\ 0) のとき 21+02=22^1+0^2=2

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

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

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

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