F2[[x]]
Spec
gcdとか, modとかができます.
Code
#include <array>
#include <cstdint>
#include <cassert>
#include <iostream>
#include <bitset>
template<const std::size_t N>
struct binfps {
using size_type = std::size_t;
using bit_type = std::uint_fast64_t;
const static size_type lg = 6;
const static size_type lgmask = (bit_type(1) << lg) - 1;
const static size_type _w_len = (N + (bit_type(1) << lg) - 1) >> lg;
std::array<bit_type, _w_len> w;
size_type len;
binfps(): len(0) {
for(size_type i = 0; i < _w_len; i++) {
w[i] = 0;
}
}
binfps(const std::bitset<N>& b) {
for(size_type i = 0; i < _w_len; i++) {
w[i] = 0;
}
for(size_type i = 0; i < N; i++) {
if(b[i]) set(i);
}
recalc();
}
int size() const { return this->len; }
void recalc() {
len = 0;
for(size_type i = w.size(); i --> 0; ) {
if(w[i]) {
for(size_type j = (1 << lg); j --> 0;) {
if(w[i] >> j) {
len = j + 1 + (i << lg);
return;
}
}
}
}
}
void set(size_type i) { w[i >> lg] |= (bit_type(1) << (i & lgmask)); }
void unset(size_type i) { w[i >> lg] &= ~(bit_type(1) << (i & lgmask)); }
bool any() const {
for(size_type i = 0; i < _w_len; i++) {
if(w[i]) {
return true;
}
}
return false;
}
bool operator[](size_type i) const {
return (w[i >> lg] >> (i & lgmask)) & 1;
}
binfps& operator^=(const binfps& b) {
for(size_type i = w.size(); i --> 0;) {
w[i] ^= b.w[i];
}
return *this;
}
binfps& operator&=(const binfps& b) {
for(size_type i = w.size(); i --> 0;) {
w[i] &= b.w[i];
}
return *this;
}
binfps& operator|=(const binfps& b) {
for(size_type i = w.size(); i --> 0;) {
w[i] &= b.w[i];
}
return *this;
}
binfps& operator<<=(size_type x) {
std::array<bit_type, _w_len> next;
for(size_type i = 0; i < _w_len; i++) {
next[i] = 0;
}
size_type off = x >> lg;
size_type m = x & lgmask;
bit_type dwmask = ((bit_type)(1) << (64 - m)) - 1;
if(m == 0) {
dwmask = ~(bit_type)(0);
}
bit_type upmask = ~dwmask;
// up
for(size_type i = 0; i + off + 1 < _w_len; i++) {
next[i + off + 1] |= (w[i] & upmask) >> (64 - m);
}
// down
for(size_type i = 0; i + off < _w_len; i++) {
next[i + off] |= (w[i] & dwmask) << m;
}
w = std::move(next);
len = std::min(N, len + x);
return (*this);
}
binfps& operator>>=(size_type x) {
std::array<bit_type, _w_len> next;
for(size_type i = 0; i < _w_len; i++) {
next[i] = 0;
}
bit_type off = x >> lg;
bit_type m = x & lgmask;
bit_type dwmask = (bit_type(1) << m) - 1;
if(m == 0) {
dwmask = 0;
}
bit_type upmask = ~dwmask;
// down
for(size_type i = 0; i + off + 1 < _w_len; i++) {
next[i] |= (w[i + off + 1] & dwmask) << (64 - m);
}
// up
for(size_type i = 0; i + off < _w_len; i++) {
next[i] |= (w[i + off] & upmask) >> m;
}
w = std::move(next);
if(len < x) {
len = 0;
}
else {
len = len - x;
}
return (*this);
}
binfps operator^(const binfps& b) const { return binfps(*this) ^= b; }
binfps operator&(const binfps& b) const { return binfps(*this) &= b; }
binfps operator|(const binfps& b) const { return binfps(*this) |= b; }
binfps operator<<(const size_type x) const { return binfps(*this) <<= x; }
binfps operator>>(const size_type x) const { return binfps(*this) >>= x; }
binfps operator~() {
binfps a = *this;
for(size_type i = w.size(); i --> 0;) {
a.w[i] = ~w[i];
}
return a;
}
bool operator<(const binfps& b) const {
bool OK = false;
for(size_type i = _w_len; i --> 0; ) {
if(w[i] != b.w[i]) {
if(w[i] < b.w[i]) {
OK = true;
}
break;
}
}
return OK;
}
bool operator<=(const binfps& b) const {
bool OK = true;
for(size_type i = _w_len; i --> 0; ) {
if(w[i] != b.w[i]) {
if(w[i] > b.w[i]) {
OK = false;
}
break;
}
}
return OK;
}
static binfps mod(binfps a, const binfps& b) {
assert(b.size() > 0);
for(int i = (int)a.size() - (int)b.size() + 1; i --> 0;) {
if(a[i + b.size() - 1]) {
a ^= (b << i);
}
}
a.recalc();
return a;
}
static binfps div(binfps a, const binfps& b) {
assert(b.size() > 0);
binfps d;
for(int i = (int)a.size() - (int)b.size() + 1; i --> 0;) {
if(a[i + b.size() - 1]) {
a ^= (b << i);
binfps e;
e.set(i);
d ^= e;
}
}
d.recalc();
return d;
}
static binfps gcd(binfps a, binfps b) {
while(b.any()) {
auto m = mod(a, b);
a = std::move(b);
b = std::move(m);
}
return a;
}
void dump() const {
for(size_type i = _w_len; i --> 0; ) {
std::cerr << std::bitset<64>(w[i]) << "|" << std::endl;
}
std::cerr << std::endl;
}
};
const int BN = 5000;
using bits = binfps<BN>;
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) noexcept {
return std::vector<T>(n, std::forward<T>(val));
}
template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept {
return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}
int main() {
i64 N;
cin >> N;
std::bitset<BN> binp;
cin >> binp;
bits X(binp);
X.recalc();
vector<bits> A(N);
rep(i,0,N) {
cin >> binp;
A[i] = bits(binp);
A[i].recalc();
}
auto G = A[0];
for(i64 i = 1; i < N; i++) {
G = bits::gcd(G, A[i]);
}
i64 ans = 0;
const i64 MOD = 998244353;
if(X.size() - G.size() + 1 >= 0) {
vector<i64> Bs(X.size() - G.size() + 1, 1);
for(i64 i = 1; i < X.size() - G.size() + 1; i++) {
Bs[i] = (Bs[i - 1] * 2) % MOD;
}
bits now;
for(i64 i = X.size() - G.size() + 1; i --> 0;) {
if(X[i + G.size() - 1]) {
ans = (ans + Bs[i]) % MOD;
}
if(now[i + G.size() - 1] != X[i + G.size() - 1]) {
now ^= (G << i);
}
}
if(now <= X) ans = (ans + 1) % MOD;
}
cout << ans << endl;
}