QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#260371#7838. 往日之影hos_lyric#40 20ms15680kbC++147.7kb2023-11-22 04:55:042024-07-04 03:08:06

Judging History

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

  • [2024-07-04 03:08:06]
  • 评测
  • 测评结果:40
  • 用时:20ms
  • 内存:15680kb
  • [2023-11-22 04:55:04]
  • 提交

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")

////////////////////////////////////////////////////////////////////////////////
// Barrett
struct ModInt {
  static unsigned M;
  static unsigned long long NEG_INV_M;
  static void setM(unsigned m) { M = m; NEG_INV_M = -1ULL / M; }
  unsigned x;
  ModInt() : x(0U) {}
  ModInt(unsigned x_) : x(x_ % M) {}
  ModInt(unsigned long long x_) : x(x_ % M) {}
  ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  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) {
    const unsigned long long y = static_cast<unsigned long long>(x) * a.x;
    const unsigned long long q = static_cast<unsigned long long>((static_cast<unsigned __int128>(NEG_INV_M) * y) >> 64);
    const unsigned long long r = y - M * q;
    x = r - M * (r >= 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; }
};
unsigned ModInt::M;
unsigned long long ModInt::NEG_INV_M;
// !!!Use ModInt::setM!!!
////////////////////////////////////////////////////////////////////////////////

using Mint = ModInt;

constexpr int LIM_INV = 1'000'010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM_INV; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM_INV; ++i) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(Int n, Int k) {
  if (n < 0) {
    if (k >= 0) {
      return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
    } else if (n - k >= 0) {
      return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
    } else {
      return 0;
    }
  } else {
    if (0 <= k && k <= n) {
      assert(n < LIM_INV);
      return fac[n] * invFac[k] * invFac[n - k];
    } else {
      return 0;
    }
  }
}


struct F {
  Mint x, y;
  F(Mint x_ = 0, Mint y_ = 0) : x(x_), y(y_) {}
  friend ostream &operator<<(ostream &os, const F &f) {
    if (!f.y) return os << f.x;
    if (!f.x) return os << f.y << "i";
    return os << f.x << "+" << f.y << "i";
  }
  F operator+(const F &f) const { return F(x + f.x, y + f.y); }
  F operator*(const F &f) const { return F(x * f.x - y * f.y, x * f.y + y * f.x); }
  F operator*(const Mint &a) const { return F(x * a, y * a); }
};

int main() {
  int numCases, MO;
  for (; ~scanf("%d%d", &numCases, &MO); ) {
    Mint::setM(MO);
    prepare();
    const F I[4] = {F(1, 0), F(0, 1), F(-1, 0), F(0, -1)};
    for (int caseId = 1; caseId <= numCases; ++caseId) {
      int N, A[4];
      scanf("%d", &N);
      for (int j = 0; j < 4; ++j) {
        scanf("%d", &A[j]);
      }
      
      /*
        i^1: at most 1
        i^3: at most 1
        i^0, i^2: not both
      */
      F ans;
      for (const int s : {0, 2}) {
        int base = 0;
        for (int j = 0; j < 4; ++j) {
          base -= A[j] * (s * j);
        }
        base &= 3;
        if (N >= (s ? 1 : 0)) {
          // 2^binom(N,2)
          const F f = I[base] * Mint(2).pow((Int)N*(N-1)/2);
// cerr<<"s="<<s<<" "<<__LINE__<<"> "<<f<<endl;
          ans = ans + f;
        }
        if (N - 1 >= (s ? 1 : 0)) {
          F f;
          for (int j1 = 0; j1 < 4; ++j1) if (A[j1]) {
            f = f + I[(base - 1 * j1) & 3] * A[j1];
          }
          // 2^binom(N-1,2) (1+i)^(N-1)
          f = f * Mint(2).pow((Int)(N-1)*(N-2)/2 + (N-1)/2) * I[((N-1)/2) & 3];
          if ((N-1) & 1) {
            f = f * F(1, 1);
          }
// cerr<<"s="<<s<<" "<<__LINE__<<"> "<<f<<endl;
          ans = ans + f;
        }
        if (N - 1 >= (s ? 1 : 0)) {
          F f;
          for (int j3 = 0; j3 < 4; ++j3) if (A[j3]) {
            f = f + I[(base - 3 * j3) & 3] * A[j3];
          }
          // 2^binom(N-1,2) (1-i)^(N-1)
          f = f * Mint(2).pow((Int)(N-1)*(N-2)/2 + (N-1)/2) * I[(-((N-1)/2)) & 3];
          if ((N-1) & 1) {
            f = f * F(1, -1);
          }
// cerr<<"s="<<s<<" "<<__LINE__<<"> "<<f<<endl;
          ans = ans + f;
        }
        if (N - 2 >= (s ? 1 : 0)) {
          F f;
          for (int j1 = 0; j1 < 4; ++j1) if (A[j1]) {
            const Mint a = A[j1];
            --A[j1];
            for (int j3 = 0; j3 < 4; ++j3) if (A[j3]) {
              const Mint aa = a * A[j3];
              f = f + I[(base - 1 * j1 - 3 * j3) & 3] * aa;
            }
            ++A[j1];
          }
          // 2^binom(N-2,2) (1+i)^(N-2) (1-i)^(N-2) 2^1
          f = f * Mint(2).pow((Int)(N-2)*(N-3)/2 + (N-2) + 1);
// cerr<<"s="<<s<<" "<<__LINE__<<"> "<<f<<endl;
          ans = ans + f;
        }
      }
      ans = ans * Mint(4).pow(-N);
// cerr<<"ans = "<<ans<<endl;
      ans = ans * Mint(2).pow(-(Int)N*(N-1)/2);
      printf("%u\n", ans.x.x);
    }
  }
  return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 7ms
memory: 15644kb

input:

1 998244353
3
1 1 0 1

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 7ms
memory: 15492kb

input:

1 998244353
7
0 2 1 4

output:

998069185

result:

ok single line: '998069185'

Test #3:

score: 0
Accepted
time: 9ms
memory: 15496kb

input:

1 998244353
4
0 1 0 3

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 7ms
memory: 15492kb

input:

1 998244353
2
1 0 1 0

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 11ms
memory: 15680kb

input:

1 998244353
6
2 1 0 3

output:

997696001

result:

ok single line: '997696001'

Test #6:

score: 0
Accepted
time: 7ms
memory: 15624kb

input:

1 998244353
2
1 0 1 0

output:

0

result:

ok single line: '0'

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 20
Accepted
time: 5ms
memory: 15664kb

input:

1 998244353
40
11 9 9 11

output:

855684614

result:

ok single line: '855684614'

Test #8:

score: 0
Accepted
time: 7ms
memory: 15548kb

input:

1 998244353
39
12 8 7 12

output:

629648158

result:

ok single line: '629648158'

Test #9:

score: 0
Accepted
time: 7ms
memory: 15640kb

input:

1 998244353
38
13 8 9 8

output:

944107686

result:

ok single line: '944107686'

Test #10:

score: 0
Accepted
time: 11ms
memory: 15532kb

input:

1 998244353
37
16 7 7 7

output:

393700837

result:

ok single line: '393700837'

Test #11:

score: 0
Accepted
time: 10ms
memory: 15492kb

input:

4 998244353
10
0 3 2 5
9
2 1 1 5
10
1 2 3 4
9
4 0 3 2

output:

124779131
998235309
124779131
998236023

result:

ok 4 lines

Test #12:

score: 0
Accepted
time: 7ms
memory: 15628kb

input:

4 998244353
10
2 1 4 3
9
1 2 4 2
10
3 2 5 0
9
3 2 2 2

output:

124779131
998239593
124778655
998236261

result:

ok 4 lines

Test #13:

score: 0
Accepted
time: 11ms
memory: 15612kb

input:

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

output:

623900891
998239355
374338940
998231025

result:

ok 4 lines

Test #14:

score: 0
Accepted
time: 7ms
memory: 15564kb

input:

8 998244353
4
2 1 0 1
4
0 2 0 2
5
0 1 1 3
4
0 1 0 3
5
1 1 0 3
5
0 3 1 1
4
2 2 0 0
5
1 1 2 1

output:

0
0
995319809
0
997269505
995319809
982646785
996294657

result:

ok 8 lines

Test #15:

score: 0
Accepted
time: 11ms
memory: 15624kb

input:

8 998244353
4
2 1 0 1
4
3 0 1 0
4
0 2 2 0
5
2 0 1 2
5
1 2 0 2
5
0 1 1 3
5
0 1 1 3
4
1 1 1 1

output:

0
0
967049217
997269505
0
995319809
995319809
0

result:

ok 8 lines

Test #16:

score: 0
Accepted
time: 7ms
memory: 15672kb

input:

3 998244353
30
1 10 7 12
8
0 3 0 5
2
0 1 0 1

output:

54137262
998208177
0

result:

ok 3 lines

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #17:

score: 0
Wrong Answer
time: 20ms
memory: 15636kb

input:

1 998244353
99
12 22 33 32
15 998244353
7
1 2 2 2
6
1 2 1 2
6
1 1 3 1
7
0 3 1 3
7
1 1 2 3
7
3 1 0 3
6
1 2 1 2
7
1 2 2 2
7
3 3 0 1
6
1 1 3 1
7
5 1 0 1
6
3 0 1 2
6
2 0 0 4
7
2 0 1 4
6
4 1 0 1

output:

940435798
998145345
997939713
997574145
998145345
998069185
998038721
997939713
998145345
998160577
997574145
998053953
997696001
997086721
997962561
997939713

result:

wrong output format Extra information in the output file

Subtask #4:

score: 10
Accepted

Test #23:

score: 10
Accepted
time: 8ms
memory: 15628kb

input:

999 999999001
2
2 0 0 0
3
3 0 0 0
4
4 0 0 0
5
5 0 0 0
6
6 0 0 0
7
7 0 0 0
8
8 0 0 0
9
9 0 0 0
10
10 0 0 0
11
11 0 0 0
12
12 0 0 0
13
13 0 0 0
14
14 0 0 0
15
15 0 0 0
16
16 0 0 0
17
17 0 0 0
18
18 0 0 0
19
19 0 0 0
20
20 0 0 0
21
21 0 0 0
22
22 0 0 0
23
23 0 0 0
24
24 0 0 0
25
25 0 0 0
26
26 0 0 0
27...

output:

499999501
874999126
359374641
919920956
691222454
586081873
33512082
496961574
790501684
206445579
708073277
492142887
486007979
21786019
802052117
198521403
854660059
658779344
904643630
538486221
357736277
949763680
94144464
342842045
695164947
276856011
552666277
813428208
572457238
910726512
177...

result:

ok 999 lines

Test #24:

score: 0
Accepted
time: 7ms
memory: 15632kb

input:

1 1000000933
154579
154579 0 0 0

output:

657848365

result:

ok single line: '657848365'

Test #25:

score: 0
Accepted
time: 11ms
memory: 15612kb

input:

1 999999001
475343
475343 0 0 0

output:

619834045

result:

ok single line: '619834045'

Test #26:

score: 0
Accepted
time: 11ms
memory: 15628kb

input:

1 999999001
165629
165629 0 0 0

output:

753727723

result:

ok single line: '753727723'

Test #27:

score: 0
Accepted
time: 11ms
memory: 15484kb

input:

1 1000000933
348634
348634 0 0 0

output:

360252198

result:

ok single line: '360252198'

Test #28:

score: 0
Accepted
time: 16ms
memory: 15636kb

input:

10000 999999229
88
88 0 0 0
96
96 0 0 0
24
24 0 0 0
95
95 0 0 0
38
38 0 0 0
27
27 0 0 0
21
21 0 0 0
76
76 0 0 0
45
45 0 0 0
72
72 0 0 0
83
83 0 0 0
78
78 0 0 0
93
93 0 0 0
73
73 0 0 0
64
64 0 0 0
71
71 0 0 0
37
37 0 0 0
42
42 0 0 0
13
13 0 0 0
19
19 0 0 0
79
79 0 0 0
65
65 0 0 0
91
91 0 0 0
28
28 0 ...

output:

228919133
233057601
14414502
12124194
609308119
236040032
384632724
342725930
359253864
890419758
438100183
233688628
152725418
662705946
267680214
513058807
175872233
462495339
413457613
571184369
442694163
537658282
297765746
578699117
239095545
57659973
903105608
745160181
652441005
521182492
347...

result:

ok 10000 lines

Test #29:

score: 0
Accepted
time: 19ms
memory: 15468kb

input:

10000 999999937
53
53 0 0 0
81
81 0 0 0
12
12 0 0 0
19
19 0 0 0
32
32 0 0 0
43
43 0 0 0
54
54 0 0 0
70
70 0 0 0
50
50 0 0 0
86
86 0 0 0
31
31 0 0 0
33
33 0 0 0
85
85 0 0 0
54
54 0 0 0
39
39 0 0 0
90
90 0 0 0
75
75 0 0 0
37
37 0 0 0
84
84 0 0 0
68
68 0 0 0
98
98 0 0 0
73
73 0 0 0
45
45 0 0 0
71
71 0 ...

output:

315851314
404961058
478608220
872834111
278393486
518892420
770069569
110378716
660680499
726285336
810531197
451629260
668208879
770069569
948485799
58650663
417912486
382928062
769177073
530030150
665011673
960730579
766994694
452899566
414064316
5286677
960730579
155111507
110378716
582367338
872...

result:

ok 10000 lines

Test #30:

score: 0
Accepted
time: 19ms
memory: 15532kb

input:

10000 1000000933
94
94 0 0 0
33
33 0 0 0
79
79 0 0 0
11
11 0 0 0
25
25 0 0 0
99
99 0 0 0
12
12 0 0 0
13
13 0 0 0
97
97 0 0 0
70
70 0 0 0
23
23 0 0 0
62
62 0 0 0
29
29 0 0 0
50
50 0 0 0
58
58 0 0 0
96
96 0 0 0
49
49 0 0 0
23
23 0 0 0
94
94 0 0 0
81
81 0 0 0
52
52 0 0 0
27
27 0 0 0
48
48 0 0 0
35
35 0...

output:

302038132
324852455
712788007
51168171
665310026
719061662
642183435
960667161
525345109
829432052
887075946
622617369
92198574
962363993
672506569
207567890
342207626
887075946
302038132
792241276
216981867
23895508
903615878
834858306
749794882
224043056
834367334
962363993
244541137
140944214
712...

result:

ok 10000 lines

Test #31:

score: 0
Accepted
time: 15ms
memory: 15488kb

input:

10000 999999229
48
48 0 0 0
99
99 0 0 0
56
56 0 0 0
82
82 0 0 0
13
13 0 0 0
78
78 0 0 0
44
44 0 0 0
23
23 0 0 0
91
91 0 0 0
39
39 0 0 0
31
31 0 0 0
39
39 0 0 0
22
22 0 0 0
69
69 0 0 0
63
63 0 0 0
49
49 0 0 0
54
54 0 0 0
91
91 0 0 0
86
86 0 0 0
14
14 0 0 0
80
80 0 0 0
47
47 0 0 0
52
52 0 0 0
56
56 0 ...

output:

969254311
41258828
420816844
53150269
413457613
233688628
16329388
962253276
297765746
579341371
491021836
579341371
694633659
238365606
737049114
282048136
467787038
297765746
568729633
239095545
37731193
985694051
20197429
420816844
467787038
337283936
131320231
267680214
890419758
12124194
757560...

result:

ok 10000 lines

Test #32:

score: 0
Accepted
time: 19ms
memory: 15620kb

input:

10000 1000000097
47
47 0 0 0
32
32 0 0 0
67
67 0 0 0
29
29 0 0 0
47
47 0 0 0
24
24 0 0 0
62
62 0 0 0
34
34 0 0 0
69
69 0 0 0
90
90 0 0 0
48
48 0 0 0
33
33 0 0 0
70
70 0 0 0
27
27 0 0 0
93
93 0 0 0
37
37 0 0 0
59
59 0 0 0
95
95 0 0 0
83
83 0 0 0
58
58 0 0 0
91
91 0 0 0
93
93 0 0 0
54
54 0 0 0
87
87 0...

output:

722092697
288259246
443086249
346535444
722092697
96701722
589679036
496735762
287843437
134626935
367894801
88663770
85448149
843667949
156786538
440592027
933702679
516941035
418538470
518055305
804803263
156786538
107212544
806586057
107212544
256264258
107212544
810269380
343546929
426066064
144...

result:

ok 10000 lines

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%