結果

問題 No.2362 Inversion Number of Mod of Linear
ユーザー LayCurse
提出日時 2023-05-08 21:21:24
言語 cLay
(20241019-1)
結果
AC  
実行時間 104 ms / 2,000 ms
コード長 5,107 bytes
コンパイル時間 3,871 ms
コンパイル使用メモリ 183,316 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-23 00:13:16
合計ジャッジ時間 4,725 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

ll T, N, M, X, Y;
ll A[1d6], B[];
ll baka1(){
  ll i, j, res = 0;
  rep(i,N) A[i] = (X*i + Y) % M;
  rep(i,N) rep(j,i+1,N) if(A[i] > A[j]) res++;
  return res;
}
ll baka2(){
  ll i, j, res = 0;
  rep(i,N) B[i] = X*i + Y;
  rep(i,N) rep(j,i+1,N) res += fDiv(B[i] + M - 1 - (B[j] % M), M) - fDiv(B[i], M);
  return res;
}
ll baka3(){
  ll i, j, res = 0;
  rep(i,N) B[i] = X*i + Y;
  rep(i,N) rep(j,i+1,N) res += fDiv(B[i] + M - 1 - B[j], M) - fDiv(B[i], M) + fDiv(B[j], M);
  return res;
}
ll baka4(){
  ll i, j, res = 0;
  rep(i,N) B[i] = X*i + Y;
  rep(i,N) res += fDiv(B[i], M) * (2 * i + 1 - N);
  rep(i,N) rep(j,i+1,N) res += fDiv(X * (i-j) + M - 1, M);
  return res;
}
ll baka5(){
  ll i, res = 0;
  rep(i,N) res += fDiv(X * i + Y, M) * (2 * i + 1 - N);
  rep(i,N) res += fDiv(-X * i + M - 1, M) * (N - i);
  return res;
}
// ordinary_floor_sum(ll n, ll m, ll a, ll b)
// = sum[k=0..n-1] floor( (a*k+b) / m )
// = num of lattice points [0 <= x < n] && [0 < y <= (Ax+B)/M]
// modified_floor_sum(ll n, ll m, ll a, ll b, ll x, ll y, ll c)
// = sum of lattice points [0 < x <= n] && [0 < y <= (Ax+B)/M] : weight of (X,Y) = x*X + y*Y + c
// = sum[X=1..n] [let Y=floor((a*x+b)/m)] (x1 * x + x0) ((y+1) * y1 + 2 * y0) y / 2
// modified_floor_sum(n,m,a,b-a,0,0,1) = ordinary_floor_sum(n,m,a,b)
// ordinary_floor_sum: n >= 0, m != 0
// modified_floor_sum: n >= 0, m != 0, other constraints?
ll baka_modified_floor_sum_bakabaka(ll n, ll m, ll a, ll b, ll x, ll y, ll c){
  ll res = 0, X, Y, h;
  rep(X,1,n+1){
    h = fDiv(a*X+b, m);
    rep(Y,1,h+1){
      res += X*x+Y*y+c;
    }
  }
  return res;
}
ll baka_modified_floor_sum(ll n, ll m, ll a, ll b, ll x, ll y, ll c){
  ll res = 0, X, Y;
  rep(X,1,n+1){
    Y = fDiv(a*X+b, m);
    res += Y * (Y+1) / 2 * y + Y * (c + x*X);
  }
  return res;
}
ll modified_floor_sum(ll n, ll m, ll a, ll b, ll x, ll y, ll c){
  ll res = 0;
  ll h, d, w, aa, bb;
  if(a < 0){
    return modified_floor_sum(n, m, -a, b + (n+1)*a, -x, y, c+x*(n+1));
  }
  h = fDiv(b, m);
  if(h){
    res += (h * n * ( (h+1)*y + (n+1)*x )) / 2 + h * n * c;
    b -= m * h;
    c += y * h;
  }
  d = fDiv(a, m);
  res += n * (n+1) / 2 * d * ( 6*c + y*(2*d*n+d+3) + (4*n+2) * x ) / 6;
  a -= d * m;
  x += d * y;
  if(a == 0) return res;
  w = fDiv(a*n+b, m);
  aa = -m;
  bb = b + a * (n+1);
  res += modified_floor_sum(w, a, aa, bb, y, -x, c+x*(n+1));
  return res;
}
ll baka6(){
  ll i, res = 0;
  rep(i,1,N+1) res += fDiv(X * i + Y - X, M) * (2 * i - 1 - N);
  rep(i,1,N+1) res += fDiv(-X * i + M - 1 + X, M) * (N - i + 1);
  return res;
}
ll baka7(){
  ll i, res = 0;
  res += modified_floor_sum(N, M, X, Y-X, 2, 0, -1-N);
  res += modified_floor_sum(N, M, -X, M-1+X, -1, 0, N+1);
  return res;
}
ll solve(){
  ll i, res = 0;
  res += modified_floor_sum(N, M, X, Y-X, 2, 0, -1-N);
  res += modified_floor_sum(N, M, -X, M-1+X, -1, 0, N+1);
  return res;
}
__int128_t modified_floor_sum128(__int128_t n, __int128_t m, __int128_t a, __int128_t b, __int128_t x, __int128_t y, __int128_t c){
  __int128_t res = 0;
  __int128_t h, d, w, aa, bb;
  if(a < 0){
    return modified_floor_sum128(n, m, -a, b + (n+1)*a, -x, y, c+x*(n+1));
  }
  h = fDiv(b, m);
  if(h){
    res += (h * n * ( (h+1)*y + (n+1)*x )) / 2 + h * n * c;
    b -= m * h;
    c += y * h;
  }
  d = fDiv(a, m);
  res += n * (n+1) / 2 * d * ( 6*c + y*(2*d*n+d+3) + (4*n+2) * x ) / 6;
  a -= d * m;
  x += d * y;
  if(a == 0) return res;
  w = fDiv(a*n+b, m);
  aa = -m;
  bb = b + a * (n+1);
  res += modified_floor_sum128(w, a, aa, bb, y, -x, c+x*(n+1));
  return res;
}
__int128_t solve128(){
  __int128_t i, res = 0;
  res += modified_floor_sum128(N, M, X, Y-X, 2, 0, -1-N);
  res += modified_floor_sum128(N, M, -X, M-1+X, -1, 0, N+1);
  return res;
}
{
  Rand rnd;
  while(0){
    ll n, m, a, b, x, y, c;
    ll r1, r2;
    n = rnd.get(1,100);
    m = rnd.get(1,100);
    a = rnd.get(-100,100);
    b = rnd.get(-100,100);
    x = rnd.get(-100,100);
    y = rnd.get(-100,100);
    c = rnd.get(-100,100);
    r1 = modified_floor_sum(n, m, a, b, x, y, c);
    r2 = baka_modified_floor_sum(n, m, a, b, x, y, c);
    wt(n,m,a,b,x,y,c);
    wt(r1,r2);
    assert(r1==r2);
  }
  
  while(0){
    N = rnd.get(1, 100);
    M = rnd.get(1, 100);
    X = rnd.get(0, (int)M-1);
    Y = rnd.get(0, (int)M-1);
    vector<long long> ans;
    ans.push_back(baka1());
    ans.push_back(baka2());
    ans.push_back(baka3());
    ans.push_back(baka4());
    ans.push_back(baka5());
    ans.push_back(baka6());
    ans.push_back(baka7());
    wt(N, M, X, Y);
    wt(ans);
    if(Distinct(ans) != 1) return 0;
  }
  while(0){
    N = rnd.get(1, 1d6);
    M = rnd.get(1, 1d6);
    X = rnd.get(0, (int)M-1);
    Y = rnd.get(0, (int)M-1);
    __int128_t r1, r2;
    r1 = solve();
    r2 = solve128();
    wt(N, M, X, Y);
    wt(r1,r2);
    if(r1 != r2) return 0;
  }
  T = cReader_ll(1, 1d4, '\n');
  rep(T){
    ll res;
    N = cReader_ll(1, 1d9, ' ');
    M = cReader_ll(1, 1d9, ' ');
    X = cReader_ll(0, M-1, ' ');
    Y = cReader_ll(0, M-1, '\n');
    res = solve128();
    wt(res);
  }
  cReader_eof();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0