結果

問題 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)
コンテスト
ユーザー 👑 ygussany
提出日時 2020-10-24 20:10:49
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 157 ms / 2,000 ms
コード長 1,339 bytes
コンパイル時間 429 ms
コンパイル使用メモリ 32,640 KB
実行使用メモリ 250,676 KB
最終ジャッジ日時 2024-07-21 15:33:45
合計ジャッジ時間 2,784 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>

const int Mod = 998244353;

void merge_sort(int x[], int n)
{
	static int y[6003] = {};
	if (n <= 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p] < x[q])? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, Q, A[6003];
	scanf("%d %d", &N, &Q);
	for (i = 1, A[0] = 0, A[N+1] = 1 << 30; i <= N; i++) scanf("%d", &(A[i]));
	merge_sort(A, N + 2);

	int j, k, l, m[2], r, p, q;
	long long ans, tmp, coeff[6001][6001];
	for (i = N - 1, coeff[N][0] = A[N] - 1, coeff[N][1] = 1; i >= 1; i--) {
		for (j = 0, coeff[i][0] = 0; j <= N - i; j++) {
			coeff[i][j+1] = coeff[i+1][j];
			coeff[i][j] = (coeff[i][j] + coeff[i+1][j] * (A[i] - 1)) % Mod;
		}
	}
	for (q = 1; q <= Q; q++) {
		scanf("%d %d %d", &l, &r, &p);
		for (j = 1; A[j] < l; j++);
		for (k = j; A[k] < r; k++);
		
		ans = 0;
		for (i = 1, tmp = 1; i < j; i++) tmp = tmp * A[i] % Mod;
		for (; j <= k && N - j + 1 >= p; tmp = tmp * A[j++] % Mod) {
			m[0] = (l > A[j-1] + 1)? l: A[j-1] + 1;
			m[1] = (r < A[j])? r: A[j];
			if ((m[1] - m[0]) % 2 == 1) continue;
			ans ^= tmp * coeff[j][p] % Mod;
		}
		printf("%lld\n", ans % Mod);
	}
	
	fflush(stdout);
	return 0;
}
0