#pragma GCC optimize("O3") #pragma GCC target("avx") #include #include #include using namespace std; typedef unsigned long long val_t; #define popcnt __builtin_popcountll //typedef unsigned int val_t; //#define popcnt __builtin_popcount //typedef mpz_class val_t; //int popcnt(const val_t &x){int r=0;val_t z=x;for(;z;z/=2)r+=z%2;return r;} int lightsout(int x,int y){ vector>a(x*y); for(int i=0;i0 ? (val_t)1<<(i-1+j*x) : 0) | (i0 ? (val_t)1<<(i+(j-1)*x) : 0) | (j0 && j>0 ? (val_t)1<<(i-1+(j-1)*x) : 0) | (i0 ? (val_t)1<<(i+1+(j-1)*x) : 0) | (i>0 && jt; vector>A; for(int i=0;i>i)&1)t.push_back(a[i][0]); else A.emplace_back(i,a[i][0]); } //解の存在判定 if(any_of(t.begin(),t.end(),[&](val_t &e)->bool{ return popcnt(e&input)&1; })){ return -1; } vectortlst(1<<(x*y-k)); // このメモリはあまり大きくならないはず for(val_t l=0;l<1<<(x*y-k);l++){ val_t r=0; for(int j=0;j