test/aoj/2981.test.cpp

• View this file on GitHub
• Last update: 2021-09-23 20:26:31+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2981

Depends on

• convolution/bitwise/and.cpp
• convolution/bitwise/fwht.cpp
• io/single.cpp
• tools/drop.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2981

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../io/single.cpp"
#include "../../tools/drop.cpp"
#include "../../convolution/bitwise/fwht.cpp"
#include "../../convolution/bitwise/and.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;
  int sz=1<<n;
  auto as=read(sz);

  auto dp(as);
  fwht(dp,bitwise_and::zeta);

  for(int i=0;i<sz;i++){
    if(!as[i]) continue;
    if(dp[i]!=(1<<(n-__builtin_popcount(i)))) drop(-1);
  }

  auto bs(as);
  for(int i=1;i<sz;i<<=1)
    for(int j=0;j<sz;j++)
      if(i&j) if(as[i^j]) bs[j]=0;

  cout<<accumulate(bs.begin(),bs.end(),0)<<endl;
  return 0;
}

#line 1 "test/aoj/2981.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2981

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "io/single.cpp"

#line 3 "io/single.cpp"
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "tools/drop.cpp"

#line 3 "tools/drop.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "convolution/bitwise/fwht.cpp"

#line 3 "convolution/bitwise/fwht.cpp"
using namespace std;
#endif
// https://kazuma8128.hatenablog.com/entry/2018/05/31/144519
//BEGIN CUT HERE
// O(n \log n)
template<typename T, typename F>
void fwht(vector<T> &as,F f){
  int n=as.size();
  for(int d=1;d<n;d<<=1)
    for(int m=d<<1,i=0;i<n;i+=m)
      for(int j=0;j<d;j++)
        f(as[i+j],as[i+j+d]);
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "convolution/bitwise/and.cpp"

#line 3 "convolution/bitwise/and.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
namespace bitwise_and{
  auto zeta=[](auto& lo,auto& hi){lo+=hi;};
  auto moebius=[](auto& lo,auto& hi){lo-=hi;};
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 11 "test/aoj/2981.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;
  int sz=1<<n;
  auto as=read(sz);

  auto dp(as);
  fwht(dp,bitwise_and::zeta);

  for(int i=0;i<sz;i++){
    if(!as[i]) continue;
    if(dp[i]!=(1<<(n-__builtin_popcount(i)))) drop(-1);
  }

  auto bs(as);
  for(int i=1;i<sz;i<<=1)
    for(int j=0;j<sz;j++)
      if(i&j) if(as[i^j]) bs[j]=0;

  cout<<accumulate(bs.begin(),bs.end(),0)<<endl;
  return 0;
}

Back to top page