問題一覧 > 通常問題

No.2362 Inversion Number of Mod of Linear

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

問題文

長さ $N$ の整数列 $A=(A_0,A_1,\ldots,A_{N-1})$ を $A_i=(iX+Y)\ \text{mod}\ M$ として定義します。

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

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

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

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

$A$ の転倒数とは

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

  • $0\le i < j < N$
  • $A_i > A_j$

制約

  • $1\le T\le 10^4$
  • $1\le N,M\le 10^9$
  • $0\le X,Y < M$

入力

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
$i$ 番目のテストケース $\text{case}_i$ は以下の形式で与えられる。 
$N$ $M$ $X$ $Y$

出力

$T$ 行出力してください。

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

サンプル

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

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

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

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

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

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