提交记录 4324


用户 题目 状态 得分 用时 内存 语言 代码长度
Dof noi18b. 【NOI2018】冒泡排序 Accepted 100 56.434 ms 14076 KB C++ 1.52 KB
提交时间 评测时间
2018-07-19 20:53:56 2020-07-31 22:52:27
#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;
const int N = 1200005, MOD = 998244353;

int tc, n;
int fac[N], ifac[N], p[N >> 1], vis[N >> 1];

inline void Read(int &x) {
  x = 0; static char c;
  for (c = getchar(); c < '0' || c > '9'; c = getchar());
  for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
}

inline int Pow(int x, int b) {
  static int re;
  for (re = 1; b; b >>= 1, x = (LL) x * x % MOD)
    if (b & 1) re = (LL) re * x % MOD;
  return re;
}

inline int C(int x, int y) {
  if (x < y) return 0;
  return (LL) fac[x] * ifac[y] % MOD * ifac[x - y] % MOD;
}
inline int Cal(int x, int y) {
  if (x < y) return 0;
  int dis = 2 * x - y, re1 = C(dis, x);
  if (y + 2 > dis) return re1;
  return (re1 - C(dis, (dis + y) / 2 + 1)) % MOD;
}

int main() {
  fac[0] = 1;
  for (int i = 1; i < N; ++i) {
    fac[i] = (LL) fac[i - 1] * i % MOD;
  }
  ifac[N - 1] = Pow(fac[N - 1], MOD - 2);
  for (int i = N - 1; i >= 1; --i) {
    ifac[i - 1] = (LL) ifac[i] * i % MOD;
  }
  
  scanf("%d", &tc);
  for (; tc; --tc) {
    int re = 0, mx = 0, low = 1, he = 0;
    memset(vis, 0, sizeof vis);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
      Read(p[i]);
    }
    for (int i = 1; i < n; ++i, --he) {
      if (mx < p[i]) he += p[i] - mx;
      mx = std::max(mx, p[i]);
      for (vis[p[i]] = 1; vis[low]; ++low);
      re = (re + Cal(n - i + 1, he + 1)) % MOD;
      if (mx > p[i] && p[i] > low) {
	break;
      }
    }
    printf("%d\n", (re + MOD) % MOD);
  }

  return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #110.147 ms11 MB + 472 KBAcceptedScore: 4

Testcase #210.146 ms11 MB + 472 KBAcceptedScore: 4

Testcase #310.15 ms11 MB + 472 KBAcceptedScore: 4

Testcase #410.148 ms11 MB + 472 KBAcceptedScore: 4

Testcase #510.147 ms11 MB + 472 KBAcceptedScore: 4

Testcase #610.148 ms11 MB + 472 KBAcceptedScore: 4

Testcase #710.145 ms11 MB + 472 KBAcceptedScore: 4

Testcase #810.147 ms11 MB + 472 KBAcceptedScore: 4

Testcase #910.148 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1010.148 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1110.148 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1210.155 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1310.158 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1410.157 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1510.158 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1610.159 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1710.204 ms11 MB + 472 KBAcceptedScore: 4

Testcase #1810.206 ms11 MB + 476 KBAcceptedScore: 4

Testcase #1910.208 ms11 MB + 476 KBAcceptedScore: 4

Testcase #2010.21 ms11 MB + 476 KBAcceptedScore: 4

Testcase #2137.04 ms12 MB + 488 KBAcceptedScore: 4

Testcase #2244.429 ms12 MB + 748 KBAcceptedScore: 4

Testcase #2353.796 ms13 MB + 160 KBAcceptedScore: 4

Testcase #2456.434 ms13 MB + 592 KBAcceptedScore: 4

Testcase #2555.762 ms13 MB + 764 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 04:57:09 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用