Submission #76586635

---

Source Code Expand

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt")

using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;

template <class T>
using vc = vector<T>;

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)

#define all(x) (x).begin(), (x).end()
#define len(x) int(x.size())

#define eb emplace_back

template <typename T, int N>
inline void hadamard_rec(T* a) {
  if constexpr (N <= 1) return;
  constexpr int H = N / 2;
  hadamard_rec<T, H>(a);
  hadamard_rec<T, H>(a + H);
  for (int i = 0; i < H; ++i) {
    auto x = a[i], y = a[H + i];
    a[i] = x + y, a[H + i] = x - y;
  }
}

template <typename T, int N = (1 << 20)>
void hadamard(vc<T>& a) {
  if constexpr (N <= 1) return;
  int n = len(a);
  if (n == N) return hadamard_rec<T, N>(a.data());
  return hadamard<T, N / 2>(a);
}

void solve() {
  int N, M;
  cin >> N >> M;
  vc<int> C(1 << M);
  FOR(i, 0, N) {
    int a;
    cin >> a;
    C[a]++;
  }

  vc<int> ids;
  FOR(i, 0, 1 << M) if (C[i] > 0) ids.eb(i);

  sort(all(ids), [&](auto& a, auto& b) -> bool { return C[a] < C[b]; });

  vc<int> D;
  for (int i : ids) {
    if (D.empty() || D.back() != C[i]) D.eb(C[i]);
  }

  int K = len(D);

  vc<u64> S(1 << M), T(1 << M);

  int B = (K + 2) / 3;
  int p = 0;
  FOR(blk, 0, B) {
    vc<int> CF;

    FOR(i, 0, 3) {
      int x = 3 * blk + i;
      if (len(D) <= x) {
        CF.eb(0);
        continue;
      }
      CF.eb(x == 0 ? D[x] : D[x] - D[x - 1]);
      while (p < len(ids) && C[ids[p]] < D[x]) ++p;
      FOR(j, p, len(ids)) S[ids[j]] |= u64(1) << (20 * i);
    }

    hadamard(S);

    const u64 base = 1 << 20;
    FOR(k, 0, 1 << M) {
      u64 x = S[k];
      u64 a = x & (base - 1);
      u64 b = (x >> 20) & (base - 1);
      u64 c = (x >> 40) & (base - 1);
      S[k] = 0;

      if (a > base - a) {
        a -= base, b += 1;
      }
      if (b > base - b) {
        b -= base, c += 1;
      }
      if (c > base - c) {
        c -= base;
      }
      T[k] += a * a * CF[0];
      T[k] += b * b * CF[1];
      T[k] += c * c * CF[2];
    }
  }
  hadamard(T);

  vc<u64> ANS(1 << M);
  FOR(i, 0, 1 << M) ANS[i] = T[i] >> (M + 1);
  ANS[0] = 0;
  FOR(i, 0, 1 << M) ANS[0] += C[i] / 2;
  
  const u32 mod = 998244353;
  reverse(ANS.begin(), ANS.end());
  u64 ans = 0;
  for(u64 x : ANS) ans = (10 * ans + x) % mod;

  cout << ans << "\n";
}

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  solve();
}

Submission Info

Judge Result