AGC030 D - Inversion Sum

「理由: AGCなので」という考察を初めてやった。
D - Inversion Sum

問題

長さNの整数列Aに対して、以下の操作をi = 1, ..., Qとして順にQ回行う。

• A[X_i]とA[Y_i]を入れかえる。あるいは何もしない。

最終的に2^Q通りの操作のしかたがあるが、それぞれについて、操作後のAの転倒数の総和をmod 10^9+7で求めよ。

解法

この手の(各操作するかしないかのn択があるときの)数え上げの計算は期待値の計算と同値。和の期待値は期待値の和なので、結局A[i] < A[j]なる(i,j)について、各操作を確率1/2で行うときに最終的に転倒する確率をmod 10^9+7で求めれば良い。
(i, j)について、A[i]とA[j]を確率1/2で交換すると、以後どのような操作を行っても転倒する確率は1/2である。このことから、P[i][j]をもともとiにあったものがjに行く確率とすると、P[i][k] * P[i][k] / 2とP[i][k] * P[j][l] (j > l)の和を求めればいいような気がしてくるが、実際そうである。(理由: AGCなので)
これを実験するとうまく行く。愚直にやるとPの計算にO(NQ)、和の計算にO(N^4)かかるが、和の計算パートは累積和をうまく管理するとO(N^2)にできる。
計算量はO(NQ + N^2)。

実装上の注意点

• 累積和の計算をバグらせないようにする。
• 添字がたくさん登場するので、間違った添字を使わないようにする。

提出: Submission #3895399 - AtCoder Grand Contest 030 (C++)

// ModInt 省略

const int N = 3010;
ModInt<> dp[N][N];
ModInt<> acc[N][N];

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  VL a(n);
  REP(i, 0, n) cin >> a[i];
  VI x(q), y(q);
  REP(i, 0, q) {
    cin >> x[i] >> y[i];
    x[i]--, y[i]--;
  }
  REP(i, 0, n) {
    dp[i][i] = 1;
  }
  ModInt<> two(2);
  ModInt<> twoinv = two.inv();
  REP(i, 0, q) {
    REP(j, 0, n) {
      ModInt<> tmp = (dp[j][x[i]] + dp[j][y[i]]) * twoinv;
      dp[j][x[i]] = tmp;
      dp[j][y[i]] = tmp;
    }
  }
  REP(i, 0, n) {
    REP(j, 0, n) acc[i][j + 1] = acc[i][j] + dp[i][j];
  }
  vector<PI> pool;
  REP(i, 0, n) pool.push_back(PI(a[i], i));
  sort(pool.rbegin(), pool.rend());
  vector<ModInt<> > tap(n + 1);
  VI que;
  // TODO proof
  ModInt<> tot = 0;
  REP(i, 0, n) {
    if (DEBUG) cerr << "pool:" << pool[i].first << " " << pool[i].second << endl;
    if (i > 0 && pool[i].first != pool[i - 1].first) {
      // tap
      for (int t: que) {
        if (DEBUG) cerr << "pushing " << t << endl;
        REP(j, 0, n + 1) {
          tap[j] += acc[t][j];
        }
      }
      que.clear();
    }
    int idx = pool[i].second;
    REP(k, 0, n) {
      tot += dp[idx][k] * tap[k];
      tot += dp[idx][k] * (tap[k + 1] - tap[k]) * twoinv;
    }
    que.push_back(idx);
  }
  REP(i, 0, q) tot *= two;
  cout << tot << endl;
}

まとめ

本番はsolved数がC < Dだったので、まずDから解いた。
手計算で仮説を確かめようとしたら計算ミスをして仮説が間違っていると勘違いしてしまい、10分くらい無駄にした。