問題一覧 > 通常問題

No.2952 Invision of Multiples

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

問題文

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

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

  • 1≤Ai≤M(1≤i≤N)1\leq A_i\leq M(1\leq i\leq N)
  • 各 ii (1≤i≤N)(1\leq i\leq N) について、 AiA_i は DiD_i の倍数
転倒数とは

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

制約

  • 2≤N≤5×1042\leq N\leq 5\times 10^4
  • 1≤M≤5×1041\leq M\leq 5\times 10^4
  • 1≤Di≤M1\leq D_i\leq M
  • 入力はすべて整数

入力

NN MM
D1D_1 D2D_2 …\dots DND_N

出力

答えを出力せよ。

サンプル

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

条件を満たす AA は以下の 66 通りあります。

  • A=(3,2,5,4)A=(3,2,5,4) のとき、転倒数は 22 です。
  • A=(3,4,5,4)A=(3,4,5,4) のとき、転倒数は 11 です。
  • A=(3,6,5,4)A=(3,6,5,4) のとき、転倒数は 33 です。
  • A=(6,2,5,4)A=(6,2,5,4) のとき、転倒数は 44 です。
  • A=(6,4,5,4)A=(6,4,5,4) のとき、転倒数は 44 です。
  • A=(6,6,5,4)A=(6,6,5,4) のとき、転倒数は 55 です。

よって答えは 2+1+3+4+4+5=192+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

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

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