oj.uz

Submission #913800

# Submission time Handle Problem Language Result Execution time Memory
913800 2024-01-20T09:31:49 Z daoquanglinh2007 Energetic turtle (IZhO11_turtle) C++17
100 / 100
 810 ms 28140 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 6e5, KM = 20;

int N, M, K, T, Z;
pii P[KM+5];
int pfac[NM+5], cnt[NM+5];
vector <int> have;
int C[KM+5][KM+5], f[KM+5][KM+5], dp[KM+5][KM+5], ans = 0;

int nCk(int n, int k){
	if (k < 0 || k > n) return 0;
	for (int i = n-k+1; i <= n; i++){
		int x = i;
		while (x > 1){
			cnt[pfac[x]]++;
			if (cnt[pfac[x]] == 1) have.push_back(pfac[x]);
			x /= pfac[x];
		}
	}
	for (int i = 2; i <= k; i++){
		int x = i;
		while (x > 1){
			cnt[pfac[x]]--;
			x /= pfac[x];
		}
	}
	int res = 1;
	for (int x : have){
		int k = cnt[x];
		cnt[x] = 0;
		while (k > 0){
			if (k&1) res = res*x%Z;
			k >>= 1;
			x = x*x%Z;
		}
	}
	return res;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> M >> K >> T >> Z;
	if (Z == 1){
		cout << 0;
		return 0;
	}
	P[0].fi = 0, P[0].se = 0;
	P[K+1].fi = N, P[K+1].se = M;
	for (int i = 1; i <= K; i++)
		cin >> P[i].fi >> P[i].se;
	sort(P, P+1+K+1);
	
	for (int i = 2; i <= N+M; i++)
		if (pfac[i] == 0){
			pfac[i] = i;
			for (int j = i*i; j <= N+M; j += i)
				pfac[j] = i;
		}
	for (int i = 0; i <= K+1; i++)
		for (int j = i; j <= K+1; j++)
			C[i][j] = nCk(P[j].fi-P[i].fi+P[j].se-P[i].se, P[j].fi-P[i].fi);
		
	for (int i = K+1; i >= 0; i--)
		for (int j = i; j <= K+1; j++){
			f[i][j] = C[i][j];
			for (int k = i+1; k < j; k++)
				f[i][j] = (f[i][j]-f[i][k]*C[k][j])%Z;
			if (f[i][j] < 0) f[i][j] += Z;
		}
		
	dp[0][0] = 1;
	for (int i = 1; i <= K+1; i++)
		for (int j = 1; j <= T+1; j++)
			for (int k = 0; k < i; k++)
				dp[i][j] = (dp[i][j]+dp[k][j-1]*f[k][i])%Z;
				
	for (int i = 1; i <= T+1; i++) ans = (ans+dp[K+1][i])%Z;
	
	cout << ans;
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 14 ms 1248 KB Output is correct
10 Correct 32 ms 1756 KB Output is correct
11 Correct 167 ms 7824 KB Output is correct
12 Correct 561 ms 27976 KB Output is correct
13 Correct 205 ms 13000 KB Output is correct
14 Correct 290 ms 12076 KB Output is correct
15 Correct 261 ms 11940 KB Output is correct
16 Correct 572 ms 27212 KB Output is correct
17 Correct 522 ms 26040 KB Output is correct
18 Correct 810 ms 26348 KB Output is correct
19 Correct 744 ms 28140 KB Output is correct
20 Correct 583 ms 26560 KB Output is correct