結果

問題 No.1696 Nonnil
ユーザー 👑 ygussanyygussany
提出日時 2021-09-26 18:22:11
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 87 ms / 3,500 ms
コード長 2,349 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 33,408 KB
実行使用メモリ 41,216 KB
最終ジャッジ日時 2024-07-19 10:17:21
合計ジャッジ時間 3,596 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

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