問題一覧 > 通常問題

No.2362 Inversion Number of Mod of Linear

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : 遭難者 / テスター : LayCurse 👑 ygussany
3 ProblemId : 9601 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-06-23 17:01:19

問題文

長さ NN の整数列 A=(A0,A1,…,AN−1)A=(A_0,A_1,\ldots,A_{N-1}) を Ai=(iX+Y) mod MA_i=(iX+Y)\ \text{mod}\ M として定義します。

この整数列 AA の転倒数を求めてください。

TT 個のテストケースが与えられるので、それぞれについて答えを求めてください。

(iX+Y) mod M(iX+Y)\ \text{mod}\ M とは

iX+Y−CiX+Y-C が MM の倍数となるような 00 以上 MM 未満の整数 CC が唯一つ存在します。この CC の値を (iX+Y) mod M(iX+Y)\ \text{mod}\ M と表記します。

AA の転倒数とは

以下の条件を全て満たす整数の組 (i,j)(i,j) の個数を指します。

  • 0≤i<j<N0\le i < j < N
  • Ai>AjA_i > A_j

制約

  • 1≤T≤1041\le T\le 10^4
  • 1≤N,M≤1091\le N,M\le 10^9
  • 0≤X,Y<M0\le X,Y < M

入力

TT
case1\text{case}_1
case2\text{case}_2
⋮\vdots
caseT\text{case}_T
ii 番目のテストケース casei\text{case}_i は以下の形式で与えられる。 
NN MM XX YY

出力

TT 行出力してください。

ii 行目 (1≤i≤T)(1\le i\le T) には、 casei\text{case}_i に対する答えを出力してください。

サンプル

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

11 つ目のテストケースでは A=(2,4,6,1,3)A=(2,4,6,1,3) です。この整数列の転倒数は 55 なので、 55 を出力してください。

22 つ目のテストケースでは A=(2,0,3,1)A=(2,0,3,1) です。この整数列の転倒数は 33 なので、 33 を出力してください。

サンプル2
入力
1
1000000 15 3 9
出力
200000200000

答えは非常に大きくなる可能性があります。

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