提交记录 6581


用户 题目 状态 得分 用时 内存 语言 代码长度
lunch noi18b. 【NOI2018】冒泡排序 Accepted 100 88.111 ms 11808 KB C++ 1.25 KB
提交时间 评测时间
2018-10-28 19:20:05 2020-08-01 00:46:14
#include<cstdio>
#include<bitset>

using namespace std;

const int N = 6e5 + 10;
const int mod = 998244353;

bitset<N> vis;

int fac[N << 1], ifac[N << 1], q[N];

int qpow(int a, int x) {
	int ret = 1;
	while(x) {
		if(x & 1) ret = 1ll * ret * a % mod;
		x >>= 1, a = 1ll * a * a % mod;
	}
	return ret;
}

void Math_Init(int n) {
	fac[0] = 1;
	for(int i = 1; i <= n; ++ i)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for(int i = n; i >= 1; -- i)
		ifac[i - 1] = 1ll * ifac[i] * i % mod;
}

int C(int n, int m) {
	return n < m ? 0 : 1ll * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}

int cal(int x, int y) {
	return x > y ? 0 : (C(x + y, y) + mod - C(x + y, y + 1)) % mod;
}

int main() {
#ifdef ylsakioi
	freopen("4769.in", "r", stdin);
	freopen("4769.out", "w", stdout);
#endif

	Math_Init((N - 5) << 1);

	int t, n, ans = 0;

	for(scanf("%d", &t); t -- ; ans = 0, vis.reset()) {

		scanf("%d", &n);
		for(int i = 1; i <= n; ++ i)
			scanf("%d", &q[i]);

		int mn = 1, mx = 0, left = 0;

		for(int i = 1; i <= n; ++ i, -- left) {
			if(q[i] > mx) left += q[i] - mx, mx = q[i];
			(ans += cal(n - i - left, n - i + 1)) %= mod;
			if(mn < q[i] && q[i] < mx) break;
			for(vis[q[i]] = 1; vis[mn]; ++ mn) ;
		}

		printf("%d\n", ans);
	}
	return 0;
}


CompilationN/AN/ACompile OKScore: N/A

Testcase #19.761 ms9 MB + 252 KBAcceptedScore: 4

Testcase #29.766 ms9 MB + 252 KBAcceptedScore: 4

Testcase #39.768 ms9 MB + 252 KBAcceptedScore: 4

Testcase #49.761 ms9 MB + 252 KBAcceptedScore: 4

Testcase #59.762 ms9 MB + 252 KBAcceptedScore: 4

Testcase #69.762 ms9 MB + 252 KBAcceptedScore: 4

Testcase #79.763 ms9 MB + 252 KBAcceptedScore: 4

Testcase #89.764 ms9 MB + 252 KBAcceptedScore: 4

Testcase #99.762 ms9 MB + 252 KBAcceptedScore: 4

Testcase #109.762 ms9 MB + 252 KBAcceptedScore: 4

Testcase #119.763 ms9 MB + 252 KBAcceptedScore: 4

Testcase #129.779 ms9 MB + 252 KBAcceptedScore: 4

Testcase #139.784 ms9 MB + 252 KBAcceptedScore: 4

Testcase #149.783 ms9 MB + 252 KBAcceptedScore: 4

Testcase #159.785 ms9 MB + 252 KBAcceptedScore: 4

Testcase #169.787 ms9 MB + 252 KBAcceptedScore: 4

Testcase #179.881 ms9 MB + 252 KBAcceptedScore: 4

Testcase #189.891 ms9 MB + 256 KBAcceptedScore: 4

Testcase #199.888 ms9 MB + 256 KBAcceptedScore: 4

Testcase #209.893 ms9 MB + 256 KBAcceptedScore: 4

Testcase #2157.675 ms10 MB + 268 KBAcceptedScore: 4

Testcase #2270.499 ms10 MB + 528 KBAcceptedScore: 4

Testcase #2384.652 ms10 MB + 964 KBAcceptedScore: 4

Testcase #2488.111 ms11 MB + 372 KBAcceptedScore: 4

Testcase #2587.262 ms11 MB + 544 KBAcceptedScore: 4


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