QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110507#5552. SkyscraperScintilla15 2ms4044kbC++142.1kb2023-06-02 17:34:422023-06-02 17:35:30

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-02 17:35:30]
  • 评测
  • 测评结果:15
  • 用时:2ms
  • 内存:4044kb
  • [2023-06-02 17:34:42]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define drep(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << ' '; cout << endl

const int P = 1e9 + 7;

const int N = 1e2 + 10;
const int M = 1e3 + 10;
const int W = 1e3;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48;
  return x * f;
}

int inc(int a, int b) { return (a += b) >= P ? a - P : a; }
int dec(int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul(int a, int b) { return 1ll * a * b % P; }
void add(int &a, int b) { (a += b) >= P ? a -= P : 1; }
void sub(int &a, int b) { (a -= b) < 0 ? a += P : 1; }
int sgn(int x) { return x & 1 ? P - 1 : 1; }
int qpow(int a, int b) { int res = 1; for (; b; b >>= 1, a = mul(a, a)) if (b & 1) res = mul(res, a); return res; }

int n, m, a[N], f[N][N][M][2][2], ans;

int main() {
  n = read(), m = read();
  rep(i, 1, n) a[i] = read();
  sort(a + 1, a + n + 1);
  f[0][0][0][0][0] = 1;
  rep(i, 0, n - 1) rep(j, 0, min(i, n - i + 1)) {
    rep(s, 0, m) rep(p, 0, 1) rep(q, 0, 1) {
      int cur = f[i][j][s][p][q], ns = s + (2 * j - p - q) * (a[i + 1] - a[i]);
      if (!cur || ns > m) continue; 
      if (!p) add(f[i + 1][j + 1][ns][1][q], cur);
      if (!q) add(f[i + 1][j + 1][ns][p][1], cur);
      add(f[i + 1][j + 1][ns][p][q], cur);
      if (!p) add(f[i + 1][j][ns][1][q], mul(cur, j - (i + 1 < n && q)));
      add(f[i + 1][j][ns][p][q], mul(cur, j - (i + 1 < n && q)));
      if (!q) add(f[i + 1][j][ns][p][1], mul(cur, j - (i + 1 < n && p)));
      add(f[i + 1][j][ns][p][q], mul(cur, j - (i + 1 < n && p)));
      if (j > 1) {
        int coef = (j - q) * (j - p) - (j - p - q) - (p && q && i + 1 < n);
        add(f[i + 1][j - 1][ns][p][q], mul(cur, coef));
      }
    }
  }
  rep(s, 0, m) add(ans, f[n][1][s][1][1]);
  printf("%d\n", ans);
  return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3556kb

input:

1 1
8

output:

0

result:

wrong answer 1st lines differ - expected: '1', found: '0'

Subtask #2:

score: 15
Accepted

Test #11:

score: 15
Accepted
time: 2ms
memory: 3744kb

input:

12 63
8 2 6 3 11 9 1 12 4 5 10 7

output:

472261248

result:

ok single line: '472261248'

Test #12:

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

input:

14 96
17 36 98 27 13 68 11 34 80 50 22 73 94 37

output:

44

result:

ok single line: '44'

Test #13:

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

input:

14 45
6 9 12 15 18 2 14 5 11 17 4 3 7 10

output:

183056086

result:

ok single line: '183056086'

Test #14:

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

input:

14 97
25 2 54 78 9 29 34 99 82 36 14 66 15 64

output:

2

result:

ok single line: '2'

Test #15:

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

input:

14 98
26 70 16 95 30 2 18 96 6 5 52 99 89 24

output:

2

result:

ok single line: '2'

Test #16:

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

input:

14 92
33 3 17 38 39 45 2 48 22 29 9 28 5 10

output:

1235526

result:

ok single line: '1235526'

Test #17:

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

input:

14 29
12 6 16 9 23 20 3 1 8 25 29 26 19 24

output:

2

result:

ok single line: '2'

Test #18:

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

input:

14 43
17 11 7 8 5 2 10 16 12 9 15 3 14 18

output:

110733412

result:

ok single line: '110733412'

Test #19:

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

input:

14 72
7 13 19 16 20 15 4 10 1 6 14 11 5 8

output:

347124497

result:

ok single line: '347124497'

Test #20:

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

input:

14 83
18 73 40 48 86 97 24 21 45 69 36 16 26 35

output:

6

result:

ok single line: '6'

Subtask #3:

score: 0
Skipped

Dependency #1:

0%