QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91165#6132. Repair the Artworkhos_lyricAC ✓284ms4812kbC++144.8kb2023-03-27 15:47:032023-03-27 15:47:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-27 15:47:04]
  • 评测
  • 测评结果:AC
  • 用时:284ms
  • 内存:4812kb
  • [2023-03-27 15:47:03]
  • 提交

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 <map>
#include <numeric>
#include <queue>
#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; }

////////////////////////////////////////////////////////////////////////////////
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 = 1'000'000'007;
using Mint = ModInt<MO>;

int N, M;
vector<int> A;

Mint dp[110][5060];

int main() {
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d%d", &N, &M);
    A.resize(N + 2);
    for (int i = 1; i <= N; ++i) {
      scanf("%d", &A[i]);
    }
    A[0] = A[N + 1] = 1;
    
    for (int i = 0; i <= N + 1; ++i) {
      for (int x = 0; x <= (i - 1) * i / 2; ++x) {
        dp[i][x] = 0;
      }
    }
    dp[0][0] = 1;
    for (int i = 0; i <= N + 1; ++i) {
      for (int j = i + 1; j <= N + 1; ++j) {
        const int dx = (j - i - 1) * (j - i) / 2;
        if (A[j] == 1) {
          for (int x = 0; x <= (i - 1) * i / 2; ++x) {
            dp[j][x + dx] += dp[i][x];
          }
          break;
        }
        if (A[j] == 2) {
          for (int x = 0; x <= (i - 1) * i / 2; ++x) {
            dp[j][x + dx] -= dp[i][x];
          }
        }
      }
    }
    
    Mint ans = 0;
    for (int x = 0; x <= N * (N + 1) / 2; ++x) {
      ans += dp[N + 1][x] * Mint(x).pow(M);
    }
    printf("%u\n", ans.x);
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3616kb

input:

3
2 2
2 0
3 2
2 1 0
3 1
2 1 0

output:

8
3
1

result:

ok 3 number(s): "8 3 1"

Test #2:

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

input:

100
2 1
0 1
2 1
2 1
2 1
1 1
1 6
2
1 14
2
3 12
2 2 2
6 13
2 2 0 2 0 2
7 14
0 0 0 0 2 2 0
5 8
2 2 0 0 0
5 5
2 2 0 0 0
12 3
0 2 0 2 2 0 1 2 2 2 2 0
7 11
2 2 0 1 0 1 0
4 4
2 1 2 2
7 5
1 1 0 0 1 0 0
2 14
2 1
15 17
2 2 1 2 0 0 0 0 2 0 1 0 0 0 0
15 11
1 1 2 0 1 2 0 0 1 0 2 1 1 1 1
15 18
1 0 1 0 2 2 1 2 0 1...

output:

1
1
0
1
1
175715347
833406719
467966815
458805426
650344
2208
537089254
146
7776
1
703335050
123067364
355668256
487954758
53774922
544070885
436748805
369291507
760487845
513270785
501075264
487417783
464534262
979007529
137956839
143317512
648268264
851188473
702545117
946416372
595191705
35054850...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 129ms
memory: 4648kb

input:

1000
20 673037423
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 774964932
2 2 2
17 730319736
2 2 1 1 2 2 2 2 2 2 2 2 2 1 2 2 1
11 893285699
2 2 2 1 2 1 2 2 2 1 2
16 98149251
1 2 1 2 1 2 1 1 2 1 2 2 2 2 1 2
7 556953277
1 2 2 1 2 2 2
3 228111342
1 1 1
11 640995044
2 2 1 1 2 2 1 1 1 1 1
19 741419324
1 1 2 ...

output:

447486147
204414804
452414918
684654914
763978130
805973365
0
922180033
214948715
401017738
0
201368027
752718484
611006275
848004989
391560729
950934074
202096866
443534870
24665646
482580424
321199514
922369975
152629767
5546104
1
194145234
1
1
1
562381239
648246425
497517379
217016206
961507095
4...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 284ms
memory: 4812kb

input:

1000
50 416236992
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 657728991
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 740461763
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

763259804
476502422
599342821
232859927
793988697
591429049
270188459
585052379
112828376
874793236
511742305
443789116
531138043
829814299
715762187
530976897
659595243
398499036
665696512
377388317
780011237
877457048
769085674
80046792
628967449
305823394
274620920
654337446
807171478
690217437
6...

result:

ok 1000 numbers

Test #5:

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

input:

1000
50 598094879
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 370102582
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 89148477
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

799398716
932856936
764416567
57812598
711885564
231337579
355184372
128337468
66039637
243697360
95147120
522827313
427687773
11613749
119992325
840421248
552748897
2153604
854978507
598264350
888588637
168914307
64499881
640494492
442303426
759524304
392240094
936658374
641034548
250860728
8449099...

result:

ok 1000 numbers