結果

問題 No.3091 The Little Match Boy
ユーザー Kude
提出日時 2025-04-06 15:52:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 3,525 bytes
コンパイル時間 4,047 ms
コンパイル使用メモリ 305,420 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-06 15:52:35
合計ジャッジ時間 5,854 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

class mint61 {
  using ull = unsigned long long;
  using ui128 = __uint128_t;

 public:
  static constexpr unsigned long long mod = (1ULL << 61) - 1;
  ull v = 0;
  constexpr mint61() {}
  explicit constexpr mint61(ull x) {
    v = (x >> 61) + (x & mod);
    if (v >= mod) v -= mod;
  }
  static constexpr mint61 raw(ull x) {
    mint61 res;
    res.v = x;
    return res;
  }
  friend constexpr mint61 operator+(mint61 lhs, mint61 rhs) {
    auto res = lhs.v + rhs.v;
    return raw(res < mod ? res : res - mod);
  }
  friend constexpr mint61 operator-(mint61 lhs, mint61 rhs) {
    return raw(lhs.v >= rhs.v ? lhs.v - rhs.v : mod + lhs.v - rhs.v);
  }
  static constexpr ull multiply_loose_mod(mint61 lhs, mint61 rhs) {
    // ab = q(m+1)+r = qm+q+r
    // q+r = ab-qm = ab-floor(ab/(m+1))m < ab-(ab/(m+1)-1)m = ab/(m+1)+m <=
    // (m-1)^2/(m+1)+m = 2m-3+4/(m+1)
    auto mul = ui128(lhs.v) * rhs.v;
    return ull(mul >> 61) + ull(mul & mod);
  }
  friend constexpr mint61 operator*(mint61 lhs, mint61 rhs) {
    auto res = multiply_loose_mod(lhs, rhs);
    return raw(res < mod ? res : res - mod);
  }
  mint61& operator+=(mint61 rhs) { return *this = *this + rhs; }
  mint61& operator-=(mint61 rhs) { return *this = *this - rhs; }
  mint61& operator*=(mint61 rhs) { return *this = *this * rhs; }
  friend constexpr bool operator==(const mint61& lhs, const mint61& rhs) {
    return lhs.v == rhs.v;
  }
  friend ostream& operator<<(ostream& os, mint61 x) { return os << x.v; }
};

std::mt19937 RNG(std::chrono::system_clock::now().time_since_epoch().count());
unsigned long long RULL(unsigned long long L, unsigned long long R) {
  assert(L < R);
  return std::uniform_int_distribution<unsigned long long>(L, R - 1)(RNG);
}

using ull = unsigned long long;
mint61 hsh[100000];

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  rep(i, 100000) hsh[i] = mint61::raw(RULL(1, mint61::mod));
  int n, m;
  cin >> n >> m;
  VI s(m);
  rep(i, m) cin >> s[i], s[i]--;
  VI pf(n), pb(n), pf_inv(n);
  rep(i, n) pf[i] = pb[i] = i;
  for (int x : s) swap(pb[x], pb[x+1]);
  rep(i, n) pf_inv[pf[i]] = i;
  mint61 now;
  rep(i, n) now += hsh[i] * mint61::raw(pb[pf[i]]);
  VL d;
  for (int i : s) {
    int a = pf_inv[i], b = pf_inv[i+1], x = pb[i], y = pb[i+1];
    now -= hsh[a] * mint61::raw(x);
    now -= hsh[b] * mint61::raw(y);
    pb[i] = y, pb[i+1] = x;
    swap(x, y);
    now += hsh[a] * mint61::raw(x);
    now += hsh[b] * mint61::raw(y);
    d.emplace_back(now.v);
    now -= hsh[a] * mint61::raw(x);
    now -= hsh[b] * mint61::raw(y);
    pf[a] = i+1, pf[b] = i;
    pf_inv[i+1] = a, pf_inv[i] = b;
    swap(a, b);
    now += hsh[a] * mint61::raw(x);
    now += hsh[b] * mint61::raw(y);
  }
  sort(all(d));
  d.erase(unique(all(d)), d.end());
  cout << d.size() << '\n';
}
0