結果

問題 No.1696 Nonnil
ユーザー 👑 ygussanyygussany
提出日時 2021-09-26 18:22:11
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 93 ms / 3,500 ms
コード長 2,349 bytes
コンパイル時間 258 ms
コンパイル使用メモリ 32,204 KB
実行使用メモリ 44,904 KB
最終ジャッジ日時 2023-09-26 16:12:42
合計ジャッジ時間 4,188 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
22,276 KB
testcase_01 AC 6 ms
22,276 KB
testcase_02 AC 6 ms
24,396 KB
testcase_03 AC 23 ms
37,984 KB
testcase_04 AC 6 ms
22,416 KB
testcase_05 AC 6 ms
22,404 KB
testcase_06 AC 6 ms
22,304 KB
testcase_07 AC 6 ms
22,396 KB
testcase_08 AC 23 ms
40,808 KB
testcase_09 AC 17 ms
27,056 KB
testcase_10 AC 24 ms
29,684 KB
testcase_11 AC 21 ms
29,396 KB
testcase_12 AC 21 ms
29,360 KB
testcase_13 AC 20 ms
29,172 KB
testcase_14 AC 75 ms
42,920 KB
testcase_15 AC 46 ms
32,944 KB
testcase_16 AC 90 ms
44,824 KB
testcase_17 AC 50 ms
42,480 KB
testcase_18 AC 58 ms
37,388 KB
testcase_19 AC 6 ms
22,360 KB
testcase_20 AC 6 ms
22,412 KB
testcase_21 AC 38 ms
38,072 KB
testcase_22 AC 57 ms
39,576 KB
testcase_23 AC 57 ms
39,172 KB
testcase_24 AC 57 ms
39,304 KB
testcase_25 AC 80 ms
43,220 KB
testcase_26 AC 58 ms
42,992 KB
testcase_27 AC 69 ms
43,416 KB
testcase_28 AC 82 ms
41,256 KB
testcase_29 AC 49 ms
40,668 KB
testcase_30 AC 42 ms
36,800 KB
testcase_31 AC 51 ms
42,248 KB
testcase_32 AC 55 ms
41,760 KB
testcase_33 AC 81 ms
42,012 KB
testcase_34 AC 41 ms
38,700 KB
testcase_35 AC 55 ms
41,560 KB
testcase_36 AC 88 ms
44,848 KB
testcase_37 AC 88 ms
44,904 KB
testcase_38 AC 88 ms
44,804 KB
testcase_39 AC 92 ms
44,892 KB
testcase_40 AC 93 ms
44,772 KB
testcase_41 AC 76 ms
35,116 KB
testcase_42 AC 21 ms
36,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int Mod = 998244353;

long long div_mod(long long x, long long y, long long z)
{
	if (x % y == 0) return x / y;
	else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}

long long pow_mod(int n, long long k)
{
	long long N, ans = 1;
	for (N = n; k > 0; k >>= 1, N = N * N % Mod) if (k & 1) ans = ans * N % Mod;
	return ans;
}

long long combination(int n, int k)
{
	long long x, y;
	for (x = 1, y = 1; k > 0; n--, k--) {
		x = x * n % Mod;
		y = y * k % Mod;
	}
	return div_mod(x, y, Mod);
}

typedef struct {
	long long key;
	int id;
} data;

void merge_sort(int n, data x[])
{
	static data y[200001] = {};
	if (n <= 1) return;
	merge_sort(n / 2, &(x[0]));
	merge_sort((n + 1) / 2, &(x[n/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].key < x[q].key)? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N, K, M, L[200001], R[200001];
	data d[200001];
	scanf("%d %d", &N, &K);
	scanf("%d", &M);
	for (i = 1; i <= M; i++) {
		scanf("%d %d", &(L[i]), &(R[i]));
		d[i-1].key = ((long long)R[i] << 30) + L[i];
		d[i-1].id = i;
	}
	merge_sort(M, d);
	
	int j, k, l, m;
	long long dp[1501][1501] = {}, dp_sum[1501][1501] = {};
	for (i = 1, dp[0][0] = 1, dp_sum[0][0] = 1; i <= K; i++) dp_sum[i][0] = 1;
	for (i = 1, l = 0, m = 0; i <= K; i++) {
		for (j = 1; j <= K; j++) {
			dp[i][j] = dp_sum[i-1][j-1] - ((l > 0)? dp_sum[l-1][j-1]: 0);
			if (dp[i][j] >= Mod) dp[i][j] -= Mod;
			else if (dp[i][j] < 0) dp[i][j] += Mod;
			dp_sum[i][j] = dp_sum[i-1][j] + dp[i][j];
			if (dp_sum[i][j] >= Mod) dp_sum[i][j] -= Mod;
		}
		if (m < M && R[d[m].id] == i) {
			while (m < M - 1 && R[d[m+1].id] == i) m++;
			k = d[m++].id;
			if (l < L[k]) l = L[k];
		}
	}
	
	long long ans = 0, perm[1501], comb[1501][1501];
	for (i = 1, comb[0][0] = 1; i <= K; i++) for (j = 1, comb[i][0] = 1, comb[i][i] = 1; j < i; j++) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % Mod;
	for (j = 2, perm[1] = 1; j <= K; j++) {
		perm[j] = pow_mod(j, N);
		for (k = j - 1; k >= 1; k--) perm[j] += Mod - perm[k] * comb[j][k] % Mod;
		perm[j] %= Mod;
	}
	for (j = 1; j <= K && j <= N; j++) ans += (dp_sum[K][j] - dp_sum[l-1][j] + Mod) * perm[j] % Mod;
	printf("%lld\n", ans % Mod);
	fflush(stdout);
	return 0;
}
0