問題一覧 > 通常問題

No.2952 Invision of Multiples

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 : nouka28nouka28 / テスター : とりゐとりゐ t9unkubjt9unkubj rotti_coderrotti_coder MichirakaraMichirakara
1 ProblemId : 10995 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-01 22:46:05

問題文

正整数 $N,M$ および正整数列 $D=(D_1,D_2,\dots,D_N)$ が与えられます。

以下の条件を満たす正整数列 $A=(A_1,A_2,\dots,A_N)$ 全てに対する転倒数の総和を $998244353$ で割ったあまりを求めてください。

  • $1\leq A_i\leq M(1\leq i\leq N)$
  • 各 $i$ $(1\leq i\leq N)$ について、 $A_i$ は $D_i$ の倍数
転倒数とは

数列 $X=(X_1,X_2,\dots,X_{|X|})$ の転倒数とは整数の組 $(i,j)(1\leq i< j\leq |X|)$ であって $A_i>A_j$ を満たすものの個数です。

制約

  • $2\leq N\leq 5\times 10^4$
  • $1\leq M\leq 5\times 10^4$
  • $1\leq D_i\leq M$
  • 入力はすべて整数

入力

$N$ $M$
$D_1$ $D_2$ $\dots$ $D_N$

出力

答えを出力せよ。

サンプル

サンプル1
入力
4 7
3 2 5 4
出力
19

条件を満たす $A$ は以下の $6$ 通りあります。

  • $A=(3,2,5,4)$ のとき、転倒数は $2$ です。
  • $A=(3,4,5,4)$ のとき、転倒数は $1$ です。
  • $A=(3,6,5,4)$ のとき、転倒数は $3$ です。
  • $A=(6,2,5,4)$ のとき、転倒数は $4$ です。
  • $A=(6,4,5,4)$ のとき、転倒数は $4$ です。
  • $A=(6,6,5,4)$ のとき、転倒数は $5$ です。

よって答えは $2+1+3+4+4+5=19$ です。

サンプル2
入力
2 1
1 1
出力
0
サンプル3
入力
10 50000
1 2 3 4 5 6 7 8 9 10
出力
292979039

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

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