CODE THANKS FESTIVAL 2017 F - Limited Xor Subset

考えたこと

数列の順番はどうでもいいのでsortできるし何なら個数だけ持ってもよさそう
sumの制約の使い方がわからなくて永遠と実験していた
実験すると規則を見つけた気になったけど試してたケースが偏ってただけだった
------解説を見て------
sumの制約からわかること
No.1 大きい数は高々n個しかない
No.2 種類数はそんなにない
No.3 O(sum)ができるので

REP(i, n) REP(j, a[i]) {
  // 処理
}

みたいなのはできる

解法1は3番を使っている
→ここまでに出てきた数のorまでを処理すればok(XORでそれ以上の数を作るのは不可能)
→計算量が
a_0 + a_0 | a_1 + … になってこれはソートされている条件で
= 2×a_0 + 2×a_1 + …
= 2×sum
= O(sum)
になって間に合う

解法2は2番を使ってる
→数列の種類数はsqrt(n)
→数字Xがcnt個あるとき、0とXが作られるパターンがそれぞれ2^(cnt-1)個
→数列の各数字についてO(sum)で処理すれば合計O(sqrt(n)sum(a))で解ける

\sum{i=0} C(cnt, i*2) = 2^{m-1}
\sum{i=0} C(cnt, i*2+1) = 2^{m-1}

N = 1 + 2 + 3 + … + M
N = M*(M+1)/2
よってM = O(sqrt(N))

あとTLで見た解法で1番を使っているのがあった
上の方のbitはそんなに表れないことを使って上の方は全列挙で下の方はDPみたいな切り替えをするらしい

数式を書いて自明な変形をするとはいみたいなパターンをいい加減解けるようになりたい

解法1

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

template<unsigned MOD>
class ModInt {
public:
  unsigned x;
  ModInt(): x(0) { }
  ModInt(signed y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {}
  unsigned get() const { return x; }

  // 逆数
  ModInt inv() const {
    ll a = 1, p = x, e = MOD-2;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    a %= MOD;
    return ModInt(a);
  }
  // e乗
  ModInt pow(ll e) {
    ll a = 1, p = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    a %= MOD;
    return ModInt(a);
  }
  // 2のx乗
  ModInt pow2() {
    ll a = 1, p = 2, e = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    a %= MOD;
    return ModInt(a);
  }

  // Comparators
  bool operator <(ModInt b) { return x < b.x; }
  bool operator >(ModInt b) { return x > b.x; }
  bool operator<=(ModInt b) { return x <= b.x; }
  bool operator>=(ModInt b) { return x >= b.x; }
  bool operator!=(ModInt b) { return x != b.x; }
  bool operator==(ModInt b) { return x == b.x; }

  // increment, decrement
  ModInt operator++() { x++; return *this; }
  ModInt operator++(int) {ModInt a = *this; x++; return a;}
  ModInt operator--() { x--; return *this; }
  ModInt operator--(int) {ModInt a = *this; x--; return a;}

  // Basic Operations
  ModInt &operator+=(ModInt that) {
    x = ((ll)x+that.x)%MOD;
    return *this;
  }
  ModInt &operator-=(ModInt that) {
    x = ((((ll)x-that.x)%MOD)+MOD)%MOD;
    return *this;
  }
  ModInt &operator*=(ModInt that) {
    x = (ll)x * that.x % MOD;
    return *this;
  }
  // O(log(mod))かかるので注意
  ModInt &operator/=(ModInt that) {
    x = (ll)x * that.inv() % MOD;
    return *this;
  }
  ModInt &operator%=(ModInt that) {
    x = (ll)x % that.x;
    return *this;
  }
  ModInt operator+(ModInt that)const{return ModInt(*this) += that;}
  ModInt operator-(ModInt that)const{return ModInt(*this) -= that;}
  ModInt operator*(ModInt that)const{return ModInt(*this) *= that;}
  ModInt operator/(ModInt that)const{return ModInt(*this) /= that;}
  ModInt operator%(ModInt that)const{return ModInt(*this) %= that;}
};
typedef ModInt<1000000007> mint;
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }

int a[100010];
mint dp[2][200010];
signed main(void)
{
  int n, k;
  cin >> n >> k;
  REP(i, n) cin >> a[i];
  sort(a, a+n);

  int cur = 1, pre = 0, lim = 0;
  dp[pre][0] = 1;
  REP(i, n) {
    REP(j, lim+1) {
      dp[cur][j] += dp[pre][j];
      dp[cur][j^a[i]] += dp[pre][j];
    }
    lim |= a[i];
    REP(j, lim+1) dp[pre][j] = 0;
    swap(cur, pre);
  }

  cout << dp[pre][k] << endl;

  return 0;
}

解法2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[100010], dp[2][200010];
unordered_map<int, int> mp;

//二分累乗法 xのe乗
ll binpow(ll x, ll e) {
  ll a = 1, p = x;
  while(e > 0) {
    if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
    else {a = (a*p) % MOD; e--;}
  }
  return a % MOD;
}

signed main(void)
{
  int n, k;
  cin >> n >> k;
  int s = 0;
  REP(i, n) cin >> a[i], mp[a[i]]++, s+=a[i];

  int cur = 1, pre = 0;
  dp[pre][0] = 1;
  for(auto i: mp) {
    REP(j, 2*s) {
      if(dp[pre][j] == 0) continue;
      (dp[cur][j] += binpow(2, i.second-1) * dp[pre][j] % MOD) %= MOD;
      (dp[cur][j^i.first] += binpow(2, i.second-1) * dp[pre][j] % MOD) %= MOD;
    }
    REP(j, 2*s) dp[pre][j] = 0;
    swap(cur, pre);
  }

  cout << dp[pre][k] << endl;

  return 0;
}

ferinの競プロ帳

競プロについてのメモ

CODE THANKS FESTIVAL 2017 F - Limited Xor Subset

考えたこと