提出 #41301769

---

ソースコード 拡げる

// O(2^N N^3)
#include <cassert>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using namespace std;

int gbit(int x, int b) { return (x >> b) & 1; }

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, M;
  cin >> N >> M;

  vector<int> S(1 << N), T(1 << N), sorted(1 << N);
  int C[32][32];
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      C[i][j] = 0;
    }
  }

  for (int i = 0; i < (1 << N); i++) {
    int p = __builtin_popcount(i);
    S[i] = i;
    T[i] = ((1 << p) - 1) << (N - p);
    for (int a = 0; a < N; a++) {
      for (int b = a + 1; b < N; b++) {
        C[a][b] += gbit(S[i], a) and !gbit(S[i], b);
      }
    }
    sorted[i] = (S[i] == T[i]);
  }

  long long last = 1;
  vector<long long> dp(1 << N);
  for (int _ = 0; _ < M; _++) {
    int a, b;
    cin >> a >> b;
    a = (a + last) % N;
    b = (b + last + last) % N;
    assert(a != b);
    if (a > b) swap(a, b);

    if (C[a][b] == 0) {
      cout << last << "\n";
      continue;
    }
    for (int i = 0; i < (1 << N); i++) {
      if (gbit(S[i], a) and !gbit(S[i], b)) {
        for (int L = 0; L < a; L++) {
          if (gbit(S[i], L)) C[L][b]--, C[L][a]++;
        }
        for (int L = a + 1; L < b; L++) {
          if (gbit(S[i], L)) C[L][b]--;
        }
        for (int R = a + 1; R < b; R++) {
          if (!gbit(S[i], R)) C[a][R]--;
        }
        for (int R = b + 1; R < N; R++) {
          if (!gbit(S[i], R)) C[a][R]--, C[b][R]++;
        }
        C[a][b]--;

        S[i] ^= (1 << a) + (1 << b);
        sorted[i] = (S[i] == T[i]);
      }
    }
    fill(begin(dp), end(dp), 0LL);
    dp[0] = 1;
    for (int i = 0; i < (1 << N); i++) {
      if (!sorted[i]) continue;
      for (int j = 0; j < N; j++) {
        if (gbit(i, j)) continue;
        int k = i + (1 << j);
        dp[k] += dp[i];
      }
    }
    cout << (last = dp.back()) << "\n";
  }
}

提出情報

ジャッジ結果