Submission #913800

#	Time	Username	Problem	Language	Result	Execution time	Memory
913800		daoquanglinh2007	Energetic turtle (IZhO11_turtle)	C++17	100 / 100	810 ms	28140 KiB

turtle

#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 / 100