QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#249833#7623. Coloring Tapehos_lyricAC ✓130ms6504kbC++146.2kb2023-11-12 16:26:312023-11-12 17:58:48

Judging History

你现在查看的是最新测评结果

  • [2023-11-12 17:58:48]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:130ms
  • 内存:6504kb
  • [2023-11-12 16:26:33]
  • 评测
  • 测评结果:100
  • 用时:130ms
  • 内存:6548kb
  • [2023-11-12 16:26:31]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;


int N, M, R;
vector<int> C, X, Y, D;

int colorss[1 << 14][14];
vector<pair<int, int>> trans[1 << 14];

int main() {
  for (; ~scanf("%d%d%d", &N, &M, &R); ) {
    C.resize(R);
    X.resize(R);
    Y.resize(R);
    D.resize(R);
    for (int r = 0; r < R; ++r) {
      scanf("%d%d%d%d", &C[r], &X[r], &Y[r], &D[r]);
      --C[r];
      --X[r];
      --Y[r];
    }
    
Int counter=0;
    for (int p = 1; p < 1 << N; p += 2) {
      vector<int> cuts;
      cuts.push_back(0);
      for (int i = 1; i < N; ++i) if (p >> i & 1) {
        cuts.push_back(i);
      }
      const int len = cuts.size();
      cuts.push_back(N);
      for (int j = 0; j < len; ++j) {
        fill(colorss[p] + cuts[j], colorss[p] + cuts[j + 1], j);
      }
      int base = 0;
      vector<int> js;
      for (int j = 0; j < len; ++j) {
        if (cuts[j + 1] - cuts[j] == 1) {
          base |= 1 << cuts[j];
        } else {
          js.push_back(j);
        }
      }
      const int jsLen = js.size();
      trans[p].clear();
      for (int q = 0; q < 1 << jsLen; ++q) {
++counter;
        int s = base, t = base;
        for (int k = 0; k < jsLen; ++k) {
          const int j = js[k];
          if (q >> k & 1) {
            s |= 1 << cuts[j];
            t |= 1 << (cuts[j + 1] - 1);
          } else {
            s |= 1 << (cuts[j + 1] - 1);
            t |= 1 << cuts[j];
          }
        }
        trans[p].emplace_back(s, t);
      }
    }
cerr<<"counter = "<<counter<<endl;
    
    vector<vector<int>> rss(M);
    for (int r = 0; r < R; ++r) {
      rss[C[r]].push_back(r);
    }
    
    bool ok0 = true;
    for (const int r : rss[0]) {
      ok0 = ok0 && ((X[r] != Y[r]) == D[r]);
    }
    
    Mint ans = 0;
    if (ok0) {
      vector<Mint> crt(1 << N, 1);
      for (int m = 1; m < M; ++m) {
        vector<Mint> nxt(1 << N, 0);
        for (int p = 1; p < 1 << N; p += 2) {
          bool ok = true;
          for (const int r : rss[m]) {
            ok = ok && ((colorss[p][X[r]] != colorss[p][Y[r]]) == D[r]);
          }
          if (ok) {
            for (const auto &e : trans[p]) {
              nxt[e.second] += crt[e.first];
            }
          }
        }
        // end some
        for (int i = 0; i < N; ++i) {
          for (int p = 0; p < 1 << N; ++p) if (!(p & 1 << i)) {
            nxt[p] += nxt[p | 1 << i];
          }
        }
        crt.swap(nxt);
      }
      ans += crt[0];
    }
    printf("%u\n", ans.x);
  }
  return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4412kb

input:

3 5 3
3 2 3 0
4 1 2 0
5 1 3 0

output:

19

result:

ok 1 number(s): "19"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4160kb

input:

5 10 10
9 3 4 1
2 4 5 0
7 2 3 0
9 2 3 0
6 3 5 0
6 2 4 1
2 4 5 0
1 1 3 1
7 2 4 0
10 2 3 0

output:

1514

result:

ok 1 number(s): "1514"

Test #3:

score: 0
Accepted
time: 1ms
memory: 4188kb

input:

5 10 20
8 4 5 0
2 2 5 1
8 4 5 0
10 3 5 0
7 1 3 1
1 2 4 1
6 3 5 1
10 3 5 0
4 1 5 1
7 3 4 1
2 2 4 1
8 3 4 0
9 3 5 0
5 2 5 1
9 4 5 0
9 1 2 0
6 1 5 1
8 3 5 0
2 2 4 1
8 3 5 0

output:

28131

result:

ok 1 number(s): "28131"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4540kb

input:

10 100 200
95 5 7 0
7 4 6 1
62 9 10 0
32 5 8 1
31 2 6 1
75 7 9 1
1 4 7 1
18 7 10 1
75 1 8 1
87 6 9 1
44 7 8 1
68 6 9 1
95 4 6 0
34 1 2 1
70 1 6 1
31 5 9 1
15 6 10 1
48 5 8 1
51 3 7 1
39 5 9 1
23 2 3 1
7 8 9 1
84 7 10 1
13 4 9 1
18 3 6 1
59 9 10 0
31 8 10 1
6 7 9 1
76 3 10 1
41 5 6 0
33 3 4 1
96 1 10...

output:

655333622

result:

ok 1 number(s): "655333622"

Test #5:

score: 0
Accepted
time: 3ms
memory: 4296kb

input:

10 200 200
106 9 10 0
93 4 10 1
199 3 7 0
73 2 9 1
105 8 9 0
38 9 10 1
73 8 10 1
153 3 9 1
123 2 5 1
159 7 9 0
154 5 7 1
162 3 7 0
113 1 5 1
131 7 9 1
67 4 6 1
178 6 10 0
157 7 9 0
147 9 10 0
154 7 10 0
123 3 4 1
39 8 10 1
139 2 9 1
191 9 10 0
36 4 5 1
17 2 8 1
124 3 7 1
9 9 10 1
71 9 10 1
181 7 8 0...

output:

552037151

result:

ok 1 number(s): "552037151"

Test #6:

score: 0
Accepted
time: 4ms
memory: 4564kb

input:

10 300 200
252 1 5 0
48 9 10 1
18 9 10 1
233 9 10 0
195 2 9 1
125 2 5 1
263 7 9 1
24 1 6 1
258 2 10 1
272 8 10 1
76 5 7 1
147 1 7 1
93 9 10 1
30 6 9 1
10 1 10 1
56 2 10 1
93 8 9 1
206 6 9 1
65 1 9 1
226 3 5 0
88 7 8 1
151 3 4 1
292 9 10 0
129 2 3 1
292 9 10 0
180 7 10 1
4 5 10 1
10 9 10 1
151 4 7 1
...

output:

4494096

result:

ok 1 number(s): "4494096"

Test #7:

score: 0
Accepted
time: 6ms
memory: 4300kb

input:

10 500 300
210 4 7 1
341 8 9 0
371 2 5 0
21 4 10 1
370 8 9 0
368 1 6 0
395 7 9 0
287 6 10 1
299 3 7 1
379 1 9 1
164 4 10 1
390 7 9 0
455 6 9 0
208 8 10 1
402 3 10 0
112 8 10 1
279 3 10 1
180 7 10 1
456 2 6 0
121 5 6 1
312 5 7 0
335 8 10 0
318 2 10 1
497 8 10 0
108 8 9 0
247 3 6 1
155 5 6 1
308 1 2 0...

output:

705403853

result:

ok 1 number(s): "705403853"

Test #8:

score: 0
Accepted
time: 25ms
memory: 4652kb

input:

12 500 300
115 3 10 1
152 10 12 1
89 8 12 1
276 4 7 0
467 6 7 0
405 5 9 0
189 4 9 1
197 1 3 1
341 7 8 0
67 7 8 1
266 2 6 1
78 8 12 1
317 11 12 0
417 8 10 0
380 2 8 0
255 2 5 1
80 7 9 1
317 5 11 1
470 5 9 0
373 3 4 0
413 4 10 0
393 9 12 0
362 8 10 1
42 7 12 1
486 3 5 0
229 1 5 0
224 6 7 0
55 3 10 1
4...

output:

378086467

result:

ok 1 number(s): "378086467"

Test #9:

score: 0
Accepted
time: 24ms
memory: 4620kb

input:

12 500 500
54 11 12 1
325 10 11 0
83 2 3 1
148 3 10 1
165 3 11 1
16 11 12 1
363 8 10 1
78 11 12 1
258 4 12 1
237 8 11 1
403 2 10 1
354 1 9 1
234 4 7 1
454 9 11 0
160 11 12 1
393 1 3 0
375 9 11 0
494 1 3 0
200 6 12 1
414 11 12 0
217 9 10 0
92 5 9 1
172 5 6 1
110 8 12 1
339 4 12 1
429 2 4 0
29 10 11 1...

output:

948753642

result:

ok 1 number(s): "948753642"

Test #10:

score: 0
Accepted
time: 122ms
memory: 6252kb

input:

14 500 500
362 4 12 1
225 5 9 1
428 5 9 1
101 8 10 1
488 5 9 0
249 11 14 1
232 2 6 1
220 4 10 1
20 7 13 1
154 4 13 1
480 8 14 0
9 2 4 1
201 7 10 1
174 10 11 0
169 13 14 0
256 10 12 1
403 11 13 0
492 10 14 0
167 6 12 1
123 11 13 1
471 9 10 0
77 5 9 1
51 6 10 1
411 11 14 1
422 11 13 0
7 1 7 1
284 5 11...

output:

103280588

result:

ok 1 number(s): "103280588"

Test #11:

score: 0
Accepted
time: 130ms
memory: 6208kb

input:

14 500 0

output:

750061283

result:

ok 1 number(s): "750061283"

Test #12:

score: 0
Accepted
time: 128ms
memory: 6264kb

input:

14 495 0

output:

662120858

result:

ok 1 number(s): "662120858"

Test #13:

score: 0
Accepted
time: 127ms
memory: 6492kb

input:

14 490 0

output:

456608006

result:

ok 1 number(s): "456608006"

Test #14:

score: 0
Accepted
time: 130ms
memory: 6208kb

input:

14 500 5
123 7 12 1
24 13 14 1
170 6 13 1
304 2 8 1
475 10 11 0

output:

715116697

result:

ok 1 number(s): "715116697"

Test #15:

score: 0
Accepted
time: 128ms
memory: 6504kb

input:

14 500 10
237 5 9 1
36 3 14 1
470 5 13 1
315 4 6 1
28 9 12 1
220 11 14 0
160 9 12 1
312 10 11 0
72 7 12 1
230 8 11 0

output:

434022866

result:

ok 1 number(s): "434022866"

Test #16:

score: 0
Accepted
time: 121ms
memory: 6456kb

input:

14 500 15
339 5 10 1
326 4 7 1
421 12 14 0
225 13 14 1
307 1 3 0
285 2 4 0
33 8 10 1
226 2 3 0
478 13 14 1
347 5 11 1
138 5 13 1
141 9 14 1
417 2 8 1
172 6 11 1
222 7 14 1

output:

268520991

result:

ok 1 number(s): "268520991"

Test #17:

score: 0
Accepted
time: 125ms
memory: 6236kb

input:

14 500 20
357 5 14 1
296 10 14 1
490 9 10 0
221 11 12 1
490 12 13 0
469 5 13 1
93 2 8 1
482 12 14 0
461 2 7 1
152 2 13 1
34 8 14 1
60 9 12 1
195 4 5 0
1 6 8 1
3 5 11 1
129 11 13 1
124 13 14 1
434 11 13 0
141 4 5 1
80 6 12 1

output:

691528902

result:

ok 1 number(s): "691528902"

Test #18:

score: 0
Accepted
time: 123ms
memory: 6172kb

input:

14 500 100
85 13 14 0
130 2 7 0
38 5 10 0
450 1 2 1
103 8 10 0
410 11 14 1
39 10 14 0
29 3 4 0
98 9 11 0
226 6 9 1
17 5 6 0
475 9 12 1
337 12 13 1
42 10 11 0
457 8 10 1
49 1 2 0
222 9 13 0
105 7 11 0
403 6 8 1
151 2 8 0
13 11 12 0
483 10 14 1
304 5 9 1
197 5 14 0
58 4 7 0
482 1 12 1
331 12 13 1
398 ...

output:

0

result:

ok 1 number(s): "0"

Test #19:

score: 0
Accepted
time: 2ms
memory: 6176kb

input:

14 498 200
457 10 13 0
163 6 10 0
23 2 5 0
109 5 8 0
113 12 14 0
294 10 12 0
1 10 14 0
451 1 2 0
275 1 13 0
345 10 14 0
171 2 9 0
392 8 11 0
184 13 14 0
328 10 11 0
84 10 13 0
238 6 12 0
306 6 13 0
56 8 14 0
404 10 14 0
90 3 10 0
446 12 14 0
303 9 11 0
71 11 12 0
362 10 13 0
405 13 14 1
258 4 13 0
1...

output:

0

result:

ok 1 number(s): "0"

Test #20:

score: 0
Accepted
time: 5ms
memory: 6124kb

input:

14 497 300
265 5 12 0
368 6 14 0
400 3 10 0
408 13 14 1
494 9 11 1
8 13 14 0
132 10 14 0
203 4 10 0
86 13 14 0
96 3 9 0
39 11 14 0
439 8 9 0
161 1 13 0
264 1 7 0
176 8 10 0
8 10 12 0
299 2 13 0
285 1 13 0
392 7 8 1
143 11 13 0
84 10 11 1
270 1 9 0
311 8 10 0
39 5 10 0
282 4 11 0
45 9 10 0
465 12 14 ...

output:

0

result:

ok 1 number(s): "0"

Test #21:

score: 0
Accepted
time: 5ms
memory: 6192kb

input:

14 499 500
349 7 10 0
440 11 13 0
391 5 11 0
461 8 10 1
172 12 14 0
139 5 10 0
79 3 4 0
456 10 11 0
276 11 14 0
484 5 6 1
178 11 13 0
295 8 11 0
384 3 8 0
112 9 11 0
170 3 7 0
490 12 14 1
243 7 9 0
360 4 7 0
302 10 12 0
266 5 8 0
350 8 12 0
282 7 12 0
480 7 11 1
312 10 13 0
356 13 14 0
277 4 5 0
245...

output:

0

result:

ok 1 number(s): "0"

Test #22:

score: 0
Accepted
time: 128ms
memory: 6492kb

input:

14 500 3
2 1 2 0
2 2 3 0
2 1 3 1

output:

0

result:

ok 1 number(s): "0"

Test #23:

score: 0
Accepted
time: 1ms
memory: 4468kb

input:

1 500 0

output:

1

result:

ok 1 number(s): "1"

Test #24:

score: 0
Accepted
time: 1ms
memory: 4408kb

input:

4 2 0

output:

17

result:

ok 1 number(s): "17"

Extra Test:

score: 0
Extra Test Passed