模板 - 基于 std::valarray 实现的矩阵

发表于 更新于 分类于 ， 本文字数： 218 阅读时长 ≈ 1 分钟

基于 C++17 标准，实现了矩阵的运算，求逆，转置，秩，行列式，Gauss 消元，支持流式 IO

仅在 GCC 下测试过

使用说明

  • 元素类型 Tp 须有接受 1 个整数的构造函数，Tp{0} 需为零元，Tp{1} 需为幺元
  • Gauss-Jordan 消元法有普通版，辗转相除版与异或版，其中普通版推荐用于浮点数，辗转相除版推荐用于整数，异或版推荐用于 bool, 这三种实现分别位于 Matrix::matrix, Matrix::matrix_int, Matrix::matrix_bool 中

成员函数 & 友元函数列表

Matrix.hview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
template <class Tp, class Iszero_t = std::function<bool(Tp)>>
class matrix {
  using self = matrix<Tp, Iszero_t>;

public:
  matrix(size_t row, size_t col, Iszero_t iszero_func, const Tp &val);
  matrix(size_t row,
         size_t col,
         Iszero_t iszero_func,
         const std::valarray<Tp> &data_);

  constexpr size_t row_size() const;
  constexpr size_t col_size() const;
  std::valarray<Tp> view() const;

  Tp &operator()(size_t r, size_t c);
  Tp operator()(size_t r, size_t c) const;

  friend std::istream &operator>>(std::istream &is, self &mat);
  friend std::ostream &operator<<(std::ostream &os, const self &mat);

  std::valarray<Tp> row(size_t r) const;
  std::valarray<Tp> col(size_t c) const;
  std::valarray<Tp> diag_cycle(ptrdiff_t d) const;
  std::slice_array<Tp> row(size_t r);
  std::slice_array<Tp> col(size_t c);
  std::slice_array<Tp> diag_cycle(ptrdiff_t d);
  std::valarray<Tp> row_varray(size_t r) const;
  std::valarray<Tp> col_varray(size_t c) const;
  std::valarray<Tp> diag_cycle_varray(ptrdiff_t d) const;
  self submatrix(size_t row_l, size_t row_r, size_t col_l, size_t col_r) const;
  std::gslice_array<Tp>
  submatrix_raw(size_t row_l, size_t row_r, size_t col_l, size_t col_r);

  friend self operator+(self lhs, const Tp &val);
  friend self operator-(self lhs, const Tp &val);
  friend self operator%(self lhs, const Tp &val);
  friend self operator*(self lhs, const Tp &val);
  friend self operator/(self lhs, const Tp &val);
  friend self operator&(self lhs, const Tp &val);
  friend self operator|(self lhs, const Tp &val);
  friend self operator^(self lhs, const Tp &val);
  friend self operator<<(self lhs, const Tp &val);
  friend self operator>>(self lhs, const Tp &val);

  friend self operator+(self lhs, const self &rhs);
  friend self operator-(self lhs, const self &rhs);
  friend self operator*(const self &lhs, const self &rhs);
  friend self operator/(const self &lhs, const self &rhs);
  friend self operator%(self lhs, const self &rhs);
  friend self operator&(self lhs, const self &rhs);
  // using gauss method to calc lhs^{-1}*rhs
  friend self operator|(const self &lhs, const self &rhs);
  friend self operator^(self lhs, const self &rhs);
  friend self operator<<(self lhs, const self &rhs);
  friend self operator>>(self lhs, const self &rhs);

  friend matrix<bool> operator==(const self &lhs, const Tp &val);
  friend matrix<bool> operator==(const self &lhs, const Tp &val);
  friend matrix<bool> operator<(const self &lhs, const Tp &val);
  friend matrix<bool> operator<=(const self &lhs, const Tp &val);
  friend matrix<bool> operator>(const self &lhs, const Tp &val);
  friend matrix<bool> operator>=(const self &lhs, const Tp &val);

  friend matrix<bool> operator==(const self &lhs, const self &rhs);
  friend matrix<bool> operator==(const self &lhs, const self &rhs);
  friend matrix<bool> operator<(const self &lhs, const self &rhs);
  friend matrix<bool> operator<=(const self &lhs, const self &rhs);
  friend matrix<bool> operator>(const self &lhs, const self &rhs);
  friend matrix<bool> operator>=(const self &lhs, const self &rhs);

  self &operator+=(const Tp &val);
  self &operator-=(const Tp &val);
  self &operator*=(const Tp &val);
  self &operator/=(const Tp &val);
  self &operator%=(const Tp &val);
  self &operator&=(const Tp &val);
  self &operator|=(const Tp &val);
  self &operator^=(const Tp &val);
  self &operator<<=(const Tp &val);
  self &operator>>=(const Tp &val);

  self &operator+=(const self &rhs);
  self &operator-=(const self &rhs);
  self &operator*=(const self &rhs);
  self &operator/=(const self &rhs);
  self &operator%=(const self &rhs);
  self &operator&=(const self &rhs);
  // using gauss method to calc lhs^{-1}*rhs
  self &operator|=(const self &rhs);
  self &operator^=(const self &rhs);
  self &operator<<=(const self &rhs);
  self &operator>>=(const self &rhs);

  // [lhs] [rhs] -> [lhs; rhs]
  friend self merge_ud(const self &lhs, const self &rhs);
  // [lhs] [rhs] -> [lhs rhs]
  friend self merge_lr(const self &lhs, const self &rhs);

  constexpr void swap_row(size_t r1, size_t r2);
  constexpr void swap_col(size_t c1, size_t c2);
  constexpr void swap_diag_cycle(size_t d1, size_t d2);

  virtual int64_t
  do_gauss_range(size_t row_start, size_t row_end, bool clear_all = true);
  ptrdiff_t do_gauss(bool clear_all = true);
  self transpose() const;
  self inverse() const;
  Tp trace() const;
  size_t rank() const;
  Tp det() const;
  friend self pow(self mat, size_t b);

protected:
  size_t r_sz, c_sz;
  Iszero_t iszero;
  std::valarray<Tp> data;
};

template <class Tp>
class matrix_int: public matrix<Tp> {
public:
  matrix_int(size_t row, size_t col, const Tp &val = Tp{});
  matrix_int(size_t row, size_t col, const std::valarray<Tp> &data_);

  int64_t do_gauss_range(size_t row_start,
                         size_t row_end,
                         bool clear_all = true) override;
};

class matrix_bool: public matrix<bool> {
public:
  matrix_bool(size_t row, size_t col, bool val = false);
  matrix_bool(size_t row, size_t col, const std::valarray<bool> &data_);

  int64_t do_gauss_range(size_t row_start,
                         size_t row_end,
                         bool clear_all = true) override;
};

代码

Show code

Matrix.hppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
namespace Matrix {
template <class Tp, class Iszero_t = std::function<bool(Tp)>>
class matrix {
#define ASSERTT_(expr, text) \
  if (!(expr)) throw std::runtime_error(text);
#define ASSERT_(expr) ASSERTT_(expr, #expr)
  using self = matrix<Tp, Iszero_t>;

protected:
  constexpr bool
  gauss_swapr__(size_t &row_, size_t row_pre_, size_t col_, size_t row_end) {
    row_ = row_pre_;
    for (size_t j = row_ + 1; j < row_end; ++j)
      if (std::abs((*this)(j, col_)) > std::abs((*this)(row_, col_))) row_ = j;
    if (row_ != row_pre_) {
      swap_row(row_, row_pre_);
      return true;
    }
    return false;
  }

protected:
  size_t r_sz, c_sz;
  Iszero_t iszero;
  std::valarray<Tp> data;

public:
  matrix(size_t row, size_t col, Iszero_t iszero_func, const Tp &val = Tp{})
    : r_sz(row), c_sz(col), iszero(iszero_func), data(val, row * col) {
    ASSERT_(row > 0 && col > 0);
  }
  matrix(size_t row,
         size_t col,
         Iszero_t iszero_func,
         const std::valarray<Tp> &data_)
    : r_sz(row), c_sz(col), iszero(iszero_func), data(data_) {
    ASSERT_(row > 0 && col > 0);
  }
  constexpr size_t row_size() const { return r_sz; }
  constexpr size_t col_size() const { return c_sz; }
  std::valarray<Tp> view() const { return data; }

  Tp &operator()(size_t r, size_t c) { return data[r * col_size() + c]; }
  Tp operator()(size_t r, size_t c) const { return data[r * col_size() + c]; }

  friend std::istream &operator>>(std::istream &is, self &mat) {
    for (auto &i : mat.data) is >> i;
    return is;
  }
  friend std::ostream &operator<<(std::ostream &os, const self &mat) {
    for (size_t i = 0; i < mat.row_size(); ++i)
      for (size_t j = 0; j < mat.col_size(); ++j)
        os << mat(i, j) << " \n"[j == mat.col_size() - 1];
    return os;
  }

#define INVOKES_SLICE__(name, para1_t, para1, ...)                             \
  std::valarray<Tp> name(para1_t para1) const __VA_ARGS__ std::slice_array<Tp> \
    name(para1_t para1) __VA_ARGS__ std::valarray<Tp> name##_varray(           \
      para1_t para1) const __VA_ARGS__

  INVOKES_SLICE__(row, size_t, r, {
    return data[std::slice(r * col_size(), col_size(), 1)];
  })
  INVOKES_SLICE__(col, size_t, c, {
    return data[std::slice(c, row_size(), col_size())];
  })
  INVOKES_SLICE__(diag_cycle, ptrdiff_t, d, {
    return data[d >= 0 ?
                  std::slice(d, row_size(), col_size() + 1) :
                  std::slice(-d * row_size(), row_size(), col_size() + 1)];
  })

#undef INVOKES_SLICE__

  self submatrix(size_t row_l, size_t row_r, size_t col_l, size_t col_r) const {
    return self(row_r - row_l,
                col_r - col_l,
                data[std::gslice(row_l * col_size() + col_l,
                                 {row_r - row_l, col_r - col_l},
                                 {col_size(), 1})],
                iszero);
  }

  std::gslice_array<Tp>
  submatrix_raw(size_t row_l, size_t row_r, size_t col_l, size_t col_r) {
    return data[std::gslice(row_l * col_size() + col_l,
                            {row_r - row_l, col_r - col_l},
                            {col_size(), 1})];
  }

#define OPB__(op)                                                              \
  friend matrix<bool> operator op(const self &lhs, const Tp &val) {            \
    return matrix<bool>(lhs.row_size(), lhs.col_size(), lhs.data op val);      \
  }                                                                            \
  friend matrix<bool> operator op(const self &lhs, const self &rhs) {          \
    ASSERT_(lhs.row_size() == rhs.row_size() &&                                \
            lhs.col_size() == rhs.col_size());                                 \
    return matrix<bool>(lhs.row_size(), lhs.col_size(), lhs.data op rhs.data); \
  }

  OPB__(==)
  OPB__(!=)
  OPB__(<)
  OPB__(<=)
  OPB__(>)
  OPB__(>=)

#undef OPB__

#define OP__(op)                                                              \
  friend self operator op(self lhs, const Tp &val) { return lhs op## = val; } \
  self &operator op##=(const Tp &val) {                                       \
    data op## = val;                                                          \
    return *this;                                                             \
  }                                                                           \
  friend self operator op(self lhs, const self &rhs) {                        \
    return lhs op## = rhs;                                                    \
  }                                                                           \
  self &operator op##=(const self &rhs) {                                     \
    ASSERT_(row_size() == rhs.row_size() && col_size() == rhs.col_size());    \
    data op## = rhs.data;                                                     \
    return *this;                                                             \
  }

  OP__(+)
  OP__(-)
  OP__(%)
  OP__(&)
  OP__(^)
  OP__(<<)
  OP__(>>)

#undef OP__

#define OPF__(op, ...)                                                         \
  friend self operator op(self lhs, const Tp &val) { return lhs op## = val; }  \
  self &operator op##=(const Tp &val) {                                        \
    data op## = val;                                                           \
    return *this;                                                              \
  }                                                                            \
  friend self operator op(const self &lhs, const self &rhs) __VA_ARGS__ self & \
  operator op##=(const self &rhs) {                                            \
    return *this = *this op rhs;                                               \
  }
  OPF__(*, {
    ASSERT_(lhs.col_size() == rhs.row_size());
    self ret(lhs.row_size(), rhs.col_size(), lhs.iszero, Tp{});
    for (size_t i = 0; i < ret.row_size(); ++i) {
      auto &&r_ = lhs.row(i);
      for (size_t j = 0; j < ret.col_size(); ++j)
        ret(i, j) = (r_ * rhs.col(j)).sum();
    }
    return ret;
  })

  OPF__(/, { return lhs * rhs.inverse(); })
  // using gauss method to calc lhs^{-1}*rhs
  OPF__(|, {
    ASSERT_(lhs.row_size() == lhs.col_size() &&
            rhs.row_size() == lhs.row_size());
    self tmp_ = merge_lr(lhs, rhs);
    ASSERTT_(std::abs(tmp_.do_gauss()) == lhs.row_size(), "Inverse not exist");
    for (size_t i = 0; i < lhs.row_size(); ++i)
      tmp_
        .data[std::slice(i * (lhs.col_size() + rhs.col_size()) + lhs.col_size(),
                         rhs.col_size(),
                         1)] /= std::valarray<Tp>(tmp_(i, i), rhs.col_size());
    return tmp_.submatrix(
      0, rhs.row_size(), lhs.col_size(), lhs.col_size() + rhs.col_size());
  })

#undef OPF__

  // [lhs] [rhs] -> [lhs; rhs]
  friend self merge_ud(const self &lhs, const self &rhs) {
    ASSERT_(lhs.col_size() == rhs.col_size());
    self ret(lhs.row_size() + rhs.row_size(), lhs.col_size(), Tp{}, lhs.iszero);
    ret.data[std::slice(0, lhs.row_size() * lhs.col_size(), 1)] = lhs.view();
    ret.data[std::slice(
      lhs.row_size() * lhs.col_size(), rhs.row_size() * rhs.col_size(), 1)] =
      rhs.view();
    return ret;
  }

  // [lhs] [rhs] -> [lhs rhs]
  friend self merge_lr(const self &lhs, const self &rhs) {
    ASSERT_(lhs.row_size() == rhs.row_size());
    self ret(lhs.row_size(), lhs.col_size() + rhs.col_size(), Tp{}, lhs.iszero);
    ret.data[std::gslice(
      0, {lhs.row_size(), lhs.col_size()}, {ret.col_size(), 1})] = lhs.view();
    ret.data[std::gslice(
      lhs.col_size(), {rhs.row_size(), rhs.col_size()}, {ret.col_size(), 1})] =
      rhs.view();
    return ret;
  }

  constexpr void swap_row(size_t r1, size_t r2) {
    if (r1 == r2) return;
    std::valarray<Tp> __ = row(r1);
    row(r1) = row(r2);
    row(r2) = __;
  }
  constexpr void swap_col(size_t c1, size_t c2) {
    if (c1 == c2) return;
    std::valarray<Tp> __ = col(c1);
    col(c1) = col(c2);
    col(c2) = __;
  }
  constexpr void swap_diag_cycle(size_t d1, size_t d2) {
    if (d1 == d2) return;
    std::valarray<Tp> __ = diag_cycle(d1);
    diag_cycle(d1) = diag_cycle(d2);
    diag_cycle(d2) = __;
  }

  virtual int64_t
  do_gauss_range(size_t row_start, size_t row_end, bool clear_all = true) {
    assert(row_start < row_end && row_end <= row_size());
    size_t rk = 0;
    bool neg = false;
    for (size_t i = row_start, now_row; i < std::min(row_end, col_size());
         ++i) {
      neg ^= gauss_swapr__(now_row, rk, i, row_end);
      if (iszero((*this)(rk, i))) continue;
      std::valarray<Tp> tmp_ =
        data[std::slice(rk * col_size() + i + 1, col_size() - i - 1, 1)];
      for (int64_t j = clear_all ? 0 : rk + 1; j < (int64_t)row_end; ++j) {
        if (j == rk || iszero((*this)(j, i))) continue;
        Tp &&_ = (*this)(j, i) / (*this)(rk, i);
        (*this)(j, i) = 0;
        data[std::slice(j * col_size() + i + 1, col_size() - i - 1, 1)] -=
          tmp_ * _;
      }
      ++rk;
    }
    return neg ? -rk : rk;
  }
  ptrdiff_t do_gauss(bool clear_all = true) {
    return do_gauss_range(0, std::min(row_size(), col_size()), clear_all);
  }

  self transpose() const {
    self ret(col_size(), row_size(), iszero, Tp{});
    for (size_t i = 0; i < row_size(); ++i) ret.col(i) = row(i);
    return ret;
  }

  self inverse() const {
    ASSERT_(row_size() == col_size());
    self ret(row_size(), col_size(), iszero, Tp{});
    ret.diag_cycle(0) = 1;
    ASSERTT_(std::abs((ret = merge_lr(*this, ret)).do_gauss()) == row_size(),
             "Inverse not exist");
    for (size_t i = 0; i < row_size(); ++i)
      ret.data[std::slice((i * 2 + 1) * col_size(), col_size(), 1)] /=
        std::valarray<Tp>(ret(i, i), col_size());
    ret = ret.submatrix(0, row_size(), col_size(), col_size() * 2);
    return ret;
  }
  Tp trace() const { return diag_cycle(0).sum(); }
  size_t rank() const { return std::abs(self(*this).do_gauss(false)); }

  Tp det() const {
    ASSERT_(row_size() == col_size());
    self tmp_(*this);
    ptrdiff_t rk_ = tmp_.do_gauss(false);
    if (std::abs(rk_) != row_size()) return Tp{};
    Tp ret = tmp_(0, 0);
    for (size_t i = 1; i < row_size(); ++i) ret *= tmp_(i, i);
    return rk_ < 0 ? -ret : ret;
  }

  friend self pow(self mat, size_t b) {
    self res(mat.row_size(), mat.col_size(), mat.iszero, Tp{});
    res.diag_cycle(0) = 1;
    for (; b; b >>= 1, mat *= mat)
      if (b & 1) res *= mat;
    return res;
  }
#undef ASSERT_
#undef ASSERTT_
};

template <class Tp>
class matrix_int: public matrix<Tp> {
  static_assert(std::is_integral<Tp>::value);

  using self = matrix_int<Tp>;
  using base = matrix<Tp>;

private:
  constexpr static auto isz__ = [](Tp const &x) { return x == 0; };

public:
  matrix_int(size_t row, size_t col, const Tp &val = Tp{})
    : base(row, col, isz__, val) {}
  matrix_int(size_t row, size_t col, const std::valarray<Tp> &data_)
    : base(row, col, isz__, data_) {}

  int64_t do_gauss_range(size_t row_start,
                         size_t row_end,
                         bool clear_all = true) override {
    assert(row_start < row_end && row_end <= this->row_size());
    int64_t rk = 0;
    bool neg = false;
    for (size_t i = row_start, now_row; i < std::min(row_end, this->col_size());
         ++i) {
      neg ^= this->gauss_swapr__(now_row, rk, i, row_end);
      if (this->iszero((*this)(rk, i))) continue;
      std::valarray<Tp> tmp_ = this->row(rk);
      for (int64_t j = clear_all ? 0 : rk; j < (int64_t)row_end; ++j) {
        if (j == rk || this->iszero((*this)(j, i))) continue;
        Tp lcm_ = std::lcm((*this)(j, i), (*this)(rk, i)),
           j_ = lcm_ / (*this)(j, i), i_ = lcm_ / (*this)(rk, i);
        this->row(j) = j_ * this->row_varray(j) - i_ * tmp_;
      }
      ++rk;
    }
    return neg ? -rk : rk;
  }
};

class matrix_bool: public matrix<bool> {
  using self = matrix_bool;
  using base = matrix<bool>;

private:
  constexpr static auto isz__ = [](bool x) { return !x; };

public:
  matrix_bool(size_t row, size_t col, bool val = false)
    : base(row, col, isz__, val) {}
  matrix_bool(size_t row, size_t col, const std::valarray<bool> &data_)
    : base(row, col, isz__, data_) {}

  int64_t do_gauss_range(size_t row_start,
                         size_t row_end,
                         bool clear_all = true) override {
    assert(row_start < row_end && row_end <= this->row_size());
    size_t rk = 0;
    bool neg = false;
    for (size_t i = row_start, now_row; i < std::min(row_end, this->col_size());
         ++i) {
      neg ^= this->gauss_swapr__(now_row, rk, i, row_end);
      if (this->iszero((*this)(rk, i))) continue;
      std::valarray<bool> tmp_ = data[std::slice(
        rk * this->col_size() + i + 1, this->col_size() - i - 1, 1)];
      for (int64_t j = clear_all ? 0 : rk + 1; j < (int64_t)row_end; ++j) {
        if (j == rk || this->iszero((*this)(j, i))) continue;
        (*this)(j, i) = false;
        data[std::slice(
          j * this->col_size() + i + 1, this->col_size() - i - 1, 1)] ^= tmp_;
      }
      ++rk;
    }
    return neg ? -rk : rk;
  }
};
}  // namespace Matrix
using Matrix::matrix, Matrix::matrix_int, Matrix::matrix_bool;

示例

Show code

Matrix_exp.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>

#include "Matrix.hpp"

using std::cin, std::cout, std::endl;

int main() {
  int n;
  cin >> n;
  matrix<double> a(
    n, n, [](double x) { return std::abs(x) <= 1e-8; }, 0);
  cin >> a;
  cout << a << endl
       << a.transpose() << endl
       << a.inverse() << endl
       << a.transpose().inverse() << endl
       << a.trace() << endl
       << a.rank() << endl
       << a.det() << endl;
  decltype(a) b(a);
  decltype(a) c(a.inverse());
  decltype(a) d(a.transpose());
  cout << a - c * d + a / c << endl
       << a - b << endl
       << a * b << endl
       << a / b << endl
       << (b | a) << endl;
  return 0;
}

  • 洛谷 P2447 [SDOI2010] 外星千足虫

    Show code

    Luogu_P2447view raw
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    /*
     * @Author: Tifa
     * @Description: From <https://github.com/Tiphereth-A/CP-archives>
     * !!! ATTENEION: All the context below is licensed under a 
     *  GNU Affero General Public License, Version 3.
     *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
     */
    #include <bits/stdc++.h>
    using namespace std;
    template <class Tp, class Iszero_t = std::function<bool(Tp)>>
    class matrix {
    #define ASSERTT_(expr, text) \
      if (!(expr)) throw std::runtime_error(text);
    #define ASSERT_(expr) ASSERTT_(expr, #expr)
      using self = matrix<Tp, Iszero_t>;

    protected:
      constexpr bool
      gauss_swapr__(size_t &row_, size_t row_pre_, size_t col_, size_t row_end) {
        row_ = row_pre_;
        for (size_t j = row_ + 1; j < row_end; ++j)
          if (std::abs((*this)(j, col_)) > std::abs((*this)(row_, col_))) row_ = j;
        if (row_ != row_pre_) {
          swap_row(row_, row_pre_);
          return true;
        }
        return false;
      }

    protected:
      size_t r_sz, c_sz;
      Iszero_t iszero;
      std::valarray<Tp> data;

    public:
      matrix(size_t row, size_t col, Iszero_t iszero_func, const Tp &val = Tp{})
        : r_sz(row), c_sz(col), iszero(iszero_func), data(val, row * col) {
        ASSERT_(row > 0 && col > 0);
      }
      matrix(size_t row,
             size_t col,
             Iszero_t iszero_func,
             const std::valarray<Tp> &data_)
        : r_sz(row), c_sz(col), iszero(iszero_func), data(data_) {
        ASSERT_(row > 0 && col > 0);
      }
      constexpr size_t row_size() const { return r_sz; }
      constexpr size_t col_size() const { return c_sz; }
      std::valarray<Tp> view() const { return data; }
      Tp &operator()(size_t r, size_t c) { return data[r * col_size() + c]; }
      Tp operator()(size_t r, size_t c) const { return data[r * col_size() + c]; }
      friend std::istream &operator>>(std::istream &is, self &mat) {
        for (auto &i : mat.data) is >> i;
        return is;
      }
      friend std::ostream &operator<<(std::ostream &os, const self &mat) {
        for (size_t i = 0; i < mat.row_size(); ++i)
          for (size_t j = 0; j < mat.col_size(); ++j)
            os << mat(i, j) << " \n"[j == mat.col_size() - 1];
        return os;
      }
    #define INVOKES_SLICE__(name, para1_t, para1, ...)                             \
      std::valarray<Tp> name(para1_t para1) const __VA_ARGS__ std::slice_array<Tp> \
        name(para1_t para1) __VA_ARGS__ std::valarray<Tp> name##_varray(           \
          para1_t para1) const __VA_ARGS__
      INVOKES_SLICE__(row, size_t, r, {
        return data[std::slice(r * col_size(), col_size(), 1)];
      })
      INVOKES_SLICE__(col, size_t, c, {
        return data[std::slice(c, row_size(), col_size())];
      })
      INVOKES_SLICE__(diag_cycle, ptrdiff_t, d, {
        return data[d >= 0 ?
                      std::slice(d, row_size(), col_size() + 1) :
                      std::slice(-d * row_size(), row_size(), col_size() + 1)];
      })
    #undef INVOKES_SLICE__
      self submatrix(size_t row_l, size_t row_r, size_t col_l, size_t col_r) const {
        return self(row_r - row_l,
                    col_r - col_l,
                    data[std::gslice(row_l * col_size() + col_l,
                                     {row_r - row_l, col_r - col_l},
                                     {col_size(), 1})],
                    iszero);
      }
      std::gslice_array<Tp>
      submatrix_raw(size_t row_l, size_t row_r, size_t col_l, size_t col_r) {
        return data[std::gslice(row_l * col_size() + col_l,
                                {row_r - row_l, col_r - col_l},
                                {col_size(), 1})];
      }
    #define OPB__(op)                                                              \
      friend matrix<bool> operator op(const self &lhs, const Tp &val) {            \
        return matrix<bool>(lhs.row_size(), lhs.col_size(), lhs.data op val);      \
      }                                                                            \
      friend matrix<bool> operator op(const self &lhs, const self &rhs) {          \
        ASSERT_(lhs.row_size() == rhs.row_size() &&                                \
                lhs.col_size() == rhs.col_size());                                 \
        return matrix<bool>(lhs.row_size(), lhs.col_size(), lhs.data op rhs.data); \
      }
      OPB__(==)
      OPB__(!=)
      OPB__(<)
      OPB__(<=)
      OPB__(>)
      OPB__(>=)
    #undef OPB__
    #define OP__(op)                                                              \
      friend self operator op(self lhs, const Tp &val) { return lhs op## = val; } \
      self &operator op##=(const Tp &val) {                                       \
        data op## = val;                                                          \
        return *this;                                                             \
      }                                                                           \
      friend self operator op(self lhs, const self &rhs) {                        \
        return lhs op## = rhs;                                                    \
      }                                                                           \
      self &operator op##=(const self &rhs) {                                     \
        ASSERT_(row_size() == rhs.row_size() && col_size() == rhs.col_size());    \
        data op## = rhs.data;                                                     \
        return *this;                                                             \
      }
      OP__(+)
      OP__(-)
      OP__(%)
      OP__(&)
      OP__(^)
      OP__(<<)
      OP__(>>)
    #undef OP__
    #define OPF__(op, ...)                                                         \
      friend self operator op(self lhs, const Tp &val) { return lhs op## = val; }  \
      self &operator op##=(const Tp &val) {                                        \
        data op## = val;                                                           \
        return *this;                                                              \
      }                                                                            \
      friend self operator op(const self &lhs, const self &rhs) __VA_ARGS__ self & \
      operator op##=(const self &rhs) {                                            \
        return *this = *this op rhs;                                               \
      }
      OPF__(*, {
        ASSERT_(lhs.col_size() == rhs.row_size());
        self ret(lhs.row_size(), rhs.col_size(), lhs.iszero, Tp{});
        for (size_t i = 0; i < ret.row_size(); ++i) {
          auto &&r_ = lhs.row(i);
          for (size_t j = 0; j < ret.col_size(); ++j)
            ret(i, j) = (r_ * rhs.col(j)).sum();
        }
        return ret;
      })
      OPF__(/, { return lhs * rhs.inverse(); })
      OPF__(|, {
        ASSERT_(lhs.row_size() == lhs.col_size() &&
                rhs.row_size() == lhs.row_size());
        self tmp_ = merge_lr(lhs, rhs);
        ASSERTT_(std::abs(tmp_.do_gauss()) == lhs.row_size(), "Inverse not exist");
        for (size_t i = 0; i < lhs.row_size(); ++i)
          tmp_
            .data[std::slice(i * (lhs.col_size() + rhs.col_size()) + lhs.col_size(),
                             rhs.col_size(),
                             1)] /= std::valarray<Tp>(tmp_(i, i), rhs.col_size());
        return tmp_.submatrix(
          0, rhs.row_size(), lhs.col_size(), lhs.col_size() + rhs.col_size());
      })
    #undef OPF__
      friend self merge_ud(const self &lhs, const self &rhs) {
        ASSERT_(lhs.col_size() == rhs.col_size());
        self ret(lhs.row_size() + rhs.row_size(), lhs.col_size(), Tp{}, lhs.iszero);
        ret.data[std::slice(0, lhs.row_size() * lhs.col_size(), 1)] = lhs.view();
        ret.data[std::slice(
          lhs.row_size() * lhs.col_size(), rhs.row_size() * rhs.col_size(), 1)] =
          rhs.view();
        return ret;
      }
      friend self merge_lr(const self &lhs, const self &rhs) {
        ASSERT_(lhs.row_size() == rhs.row_size());
        self ret(lhs.row_size(), lhs.col_size() + rhs.col_size(), Tp{}, lhs.iszero);
        ret.data[std::gslice(
          0, {lhs.row_size(), lhs.col_size()}, {ret.col_size(), 1})] = lhs.view();
        ret.data[std::gslice(
          lhs.col_size(), {rhs.row_size(), rhs.col_size()}, {ret.col_size(), 1})] =
          rhs.view();
        return ret;
      }
      constexpr void swap_row(size_t r1, size_t r2) {
        std::valarray<Tp> __ = row(r1);
        row(r1) = row(r2);
        row(r2) = __;
      }
      constexpr void swap_col(size_t c1, size_t c2) {
        std::valarray<Tp> __ = col(c1);
        col(c1) = col(c2);
        col(c2) = __;
      }
      constexpr void swap_diag_cycle(size_t d1, size_t d2) {
        std::valarray<Tp> __ = diag_cycle(d1);
        diag_cycle(d1) = diag_cycle(d2);
        diag_cycle(d2) = __;
      }
      virtual ptrdiff_t
      do_gauss_range(size_t row_start, size_t row_end, bool clear_all = true) {
        assert(row_start < row_end && row_end <= row_size());
        size_t rk = 0;
        bool neg = false;
        for (size_t i = row_start, now_row; i < std::min(row_end, col_size());
             ++i) {
          neg ^= gauss_swapr__(now_row, rk, i, row_end);
          if (iszero((*this)(rk, i))) continue;
          std::valarray<Tp> tmp_ =
            data[std::slice(rk * col_size() + i + 1, col_size() - i - 1, 1)];
          for (size_t j = clear_all ? 0 : rk + 1; j < row_end; ++j) {
            if (j == rk || iszero((*this)(j, i))) continue;
            Tp &&_ = (*this)(j, i) / (*this)(rk, i);
            (*this)(j, i) = 0;
            data[std::slice(j * col_size() + i + 1, col_size() - i - 1, 1)] -=
              tmp_ * _;
          }
          ++rk;
        }
        return neg ? -ptrdiff_t(rk) : ptrdiff_t(rk);
      }
      ptrdiff_t do_gauss(bool clear_all = true) {
        return do_gauss_range(0, std::min(row_size(), col_size()), clear_all);
      }
      self transpose() const {
        self ret(col_size(), row_size(), iszero, Tp{});
        for (size_t i = 0; i < row_size(); ++i) ret.col(i) = row(i);
        return ret;
      }
      self inverse() const {
        ASSERT_(row_size() == col_size());
        self ret(row_size(), col_size(), iszero, Tp{});
        ret.diag_cycle(0) = 1;
        ASSERTT_(std::abs((ret = merge_lr(*this, ret)).do_gauss()) == row_size(),
                 "Inverse not exist");
        for (size_t i = 0; i < row_size(); ++i)
          ret.data[std::slice((i * 2 + 1) * col_size(), col_size(), 1)] /=
            std::valarray<Tp>(ret(i, i), col_size());
        ret = ret.submatrix(0, row_size(), col_size(), col_size() * 2);
        return ret;
      }
      Tp trace() const { return diag_cycle(0).sum(); }
      size_t rank() const { return std::abs(self(*this).do_gauss(false)); }
      Tp det() const {
        ASSERT_(row_size() == col_size());
        self tmp_(*this);
        ptrdiff_t rk_ = tmp_.do_gauss(false);
        if (std::abs(rk_) != row_size()) return Tp{};
        Tp ret = tmp_(0, 0);
        for (size_t i = 1; i < row_size(); ++i) ret *= tmp_(i, i);
        return rk_ < 0 ? -ret : ret;
      }
      friend self pow(self mat, size_t b) {
        self res(mat.row_size(), mat.col_size(), mat.iszero, Tp{});
        res.diag_cycle(0) = 1;
        for (; b; b >>= 1, mat *= mat)
          if (b & 1) res *= mat;
        return res;
      }
    #undef ASSERT_
    #undef ASSERTT_
    };
    class matrix_bool: public matrix<bool> {
      using self = matrix_bool;
      using base = matrix<bool>;

    private:
      constexpr static auto isz__ = [](bool x) { return !x; };

    public:
      matrix_bool(size_t row, size_t col, bool val = false)
        : base(row, col, isz__, val) {}
      matrix_bool(size_t row, size_t col, const std::valarray<bool> &data_)
        : base(row, col, isz__, data_) {}
      ptrdiff_t do_gauss_range(size_t row_start,
                               size_t row_end,
                               bool clear_all = true) override {
        assert(row_start < row_end && row_end <= row_size());
        size_t rk = 0;
        bool neg = false;
        for (size_t i = row_start, now_row; i < std::min(row_end, col_size());
             ++i) {
          neg ^= gauss_swapr__(now_row, rk, i, row_end);
          if (iszero((*this)(rk, i))) continue;
          std::valarray<bool> tmp_ =
            data[std::slice(rk * col_size() + i + 1, col_size() - i - 1, 1)];
          for (size_t j = clear_all ? 0 : rk + 1; j < row_end; ++j) {
            if (j == rk || iszero((*this)(j, i))) continue;
            (*this)(j, i) = false;
            data[std::slice(j * col_size() + i + 1, col_size() - i - 1, 1)] ^= tmp_;
          }
          ++rk;
        }
        return neg ? -ptrdiff_t(rk) : ptrdiff_t(rk);
      }
    };
    auto solve([[maybe_unused]] int t_ = 0) -> void {
      int n, m;
      cin >> n >> m;
      matrix_bool mat(m, n + 1);
      string s;
      for (int i = 0, x; i < m; ++i) {
        cin >> s >> x;
        for (int j = 0; j < n; ++j) mat(i, j) = s[j] & 1;
        mat(i, n) = x;
      }
      int cnt = n, last_rk = 0;
      while ((last_rk = abs(mat.do_gauss_range(0, n))) != n) {
        for (int i = last_rk; i < n; ++i) {
          if (cnt >= m) {
            cout << "Cannot Determine\n";
            return;
          }
          mat.swap_row(i, cnt++);
          if (cnt >= m) {
            cout << "Cannot Determine\n";
            return;
          }
        }
      }
      cout << cnt << '\n';
      for (int i = 0; i < n; ++i) cout << (mat(i, n) ? "?y7M#" : "Earth") << '\n';
    }
    int main() {
      std::ios::sync_with_stdio(false);
      std::cin.tie(nullptr);
      int i_ = 0;
      solve(i_);
      return 0;
    }