結果

問題 No.2362 Inversion Number of Mod of Linear
ユーザー LayCurseLayCurse
提出日時 2023-05-08 21:21:24
言語 cLay
(20240104-1)
結果
AC  
実行時間 132 ms / 2,000 ms
コード長 5,107 bytes
コンパイル時間 4,045 ms
コンパイル使用メモリ 180,036 KB
実行使用メモリ 9,944 KB
最終ジャッジ日時 2023-09-05 03:29:11
合計ジャッジ時間 5,192 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
9,476 KB
testcase_01 AC 2 ms
9,480 KB
testcase_02 AC 2 ms
9,532 KB
testcase_03 AC 59 ms
9,864 KB
testcase_04 AC 21 ms
9,648 KB
testcase_05 AC 9 ms
9,476 KB
testcase_06 AC 132 ms
9,944 KB
testcase_07 AC 45 ms
9,684 KB
testcase_08 AC 38 ms
9,764 KB
testcase_09 AC 39 ms
9,704 KB
権限があれば一括ダウンロードができます

ソースコード

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();
}
0