結果
| 問題 |
No.184 たのしい排他的論理和(HARD)
|
| コンテスト | |
| ユーザー |
 polyomino_24
|
| 提出日時 | 2019-09-17 03:22:40 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,775 bytes |
| コンパイル時間 | 1,676 ms |
| コンパイル使用メモリ | 131,080 KB |
| 最終ジャッジ日時 | 2025-01-07 18:26:13 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 WA * 6 |
ソースコード
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
os << '(' << a.first << ',' << a.second << ')';
return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
for (auto x : v) os << x << ' ';
return os;
}
void debug() {
cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
cerr << a;
if (sizeof...(b)) cerr << ", ";
debug(b...);
}
#ifdef DEBUG
template<typename T>
class Vec : public vector<T>{
public:
Vec(){}
Vec(int n):vector<T>(n){}
Vec(int n, T a):vector<T>(n,a){}
T& operator[](long long n){
if(n < 0 or n >= this->size())throw out_of_range("Vec");
return this->at(n);
}
const T& operator[](long long n)const{
if(n < 0 or n >= this->size())throw out_of_range("Vec");
return this->at(n);
}
};
#define vector Vec
template<typename T>
ostream &operator<<(ostream &os, set<T> st) {
for(auto x : st) cerr << x << ' ';
return os;
}
template<typename T, typename S>
ostream &operator<<(ostream &os, map<T, S> mp) {
for(auto x : mp) cerr << x << ' ';
return os;
}
#endif
//負の数を掛けたりするとバグる
template<int MOD>
class Modint{
public:
int a;
Modint(const long long v = 0):a(v % MOD){}
int getmod() const{
return MOD;
}
Modint operator+(const Modint rhs) const{
return Modint(*this) += rhs;
}
Modint operator-(const Modint rhs) const{
return Modint(*this) -= rhs;
}
Modint operator*(const Modint rhs) const{
return Modint(*this) *= rhs;
}
Modint operator/(const Modint rhs) const{
return Modint(*this) /= rhs;
}
Modint operator+(const long long rhs) const{
return Modint(*this) += rhs;
}
Modint operator-(const long long rhs) const{
return Modint(*this) -= rhs;
}
Modint operator*(const long long rhs) const{
return Modint(*this) *= rhs;
}
Modint operator/(const long long rhs) const{
return Modint(*this) /= rhs;
}
friend Modint operator+(const long long a, const Modint b){
return b + a;
}
friend Modint operator-(const long long a, const Modint b){
return -b + a;
}
friend Modint operator*(const long long a, const Modint b){
return b * a;
}
friend Modint operator/(const long long a, const Modint b){
return Modint(a) / b;
}
Modint &operator+=(const Modint rhs){
a += rhs.a;
if(a >= MOD){
a -= MOD;
}
return *this;
}
Modint &operator-=(const Modint rhs){
if(a < rhs.a){
a += MOD;
}
a -= rhs.a;
return *this;
}
Modint &operator*=(const Modint rhs){
a = (long long)a * rhs.a % MOD;
return *this;
}
Modint &operator/=(Modint rhs){
int x = MOD - 2;
while(x){
if(x % 2){
*this *= rhs;
}
rhs *= rhs;
x /= 2;
}
return *this;
}
Modint &operator++(){
*this += 1;
return *this;
}
Modint &operator--(){
*this -= 1;
return *this;
}
Modint operator++(int){
Modint res = *this;
++(*this);
return res;
}
Modint operator--(int){
Modint res = *this;
--(*this);
return res;
}
Modint &operator+=(const long long rhs){
*this += Modint(rhs);
return *this;
}
Modint &operator-=(const long long rhs){
*this -= Modint(rhs);
return *this;
}
Modint &operator*=(const long long rhs){
*this *= Modint(rhs);
return *this;
}
Modint &operator/=(const long long rhs){
*this /= Modint(rhs);
return *this;
}
Modint operator+() const{
return *this;
}
Modint operator-() const{
return Modint()-*this;
}
bool operator==(const Modint rhs) const{
return a == rhs.a;
}
bool operator==(const long long rhs) const{
return a == rhs;
}
friend bool operator==(const long long a, const Modint b){
return a == b.a;
}
bool operator!=(const Modint rhs) const{
return a != rhs.a;
}
bool operator!=(const long long rhs) const{
return a != rhs;
}
friend ostream &operator<<(ostream &os, const Modint x){
os << x.a;
return os;
}
friend istream &operator>>(istream &is, Modint &x){
is >> x.a;
return is;
}
explicit operator bool() const{
return a > 0;
}
bool operator!(){
return a == 0;
}
explicit operator int() const{
return a;
}
explicit operator long long() const{
return (long long) a;
}
friend Modint pow(Modint a, long long b){
Modint res = 1;
while(b){
if(b % 2){
res *= a;
}
a *= a;
b /= 2;
}
return res;
}
};
using mint = Modint<2>;
int gauss(vector<vector<mint>>a){
int n = (int) a.size();
int m = (int) a[0].size();
for(int i = 0; i < m; i++){
for(int j = i; j < n; j++){
if(a[j][i]){
for(int k = i; k < m; k++){
swap(a[i][k], a[j][k]);
}
}
}
if(i >= n or !a[i][i])continue;
mint inv = mint(1) / a[i][i];
for(int j = 0; j < n; j++){
if(j != i and a[j][i]){
mint coef = a[j][i] * inv;
for(int k = i; k < m; k++){
a[j][k] = a[j][k] - coef * a[i][k];
}
}
}
}
int res = 0;
for(int i = 0; i < n and i < m; i++)if(a[i][i])res++;
return res;
}
int main(){
int n;
cin >> n;
vector<vector<mint>> a;
a.resize(n,vector<mint>(60));
rep(i,n){
ll x;
cin >> x;
rep(j,60){
if(x >> j & 1){
a[i][j] = 1;
}
}
}
cout << (1LL<<gauss(a)) << endl;
}