Submission #574620

#	Time	Username	Problem	Language	Result	Execution time	Memory
574620		penguinhacker	Energetic turtle (IZhO11_turtle)	C++14	100 / 100	243 ms	12108 KiB

turtle

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=3e5;
int n, m, k, t, z, cnt[2*mxN+1];
ar<int, 2> cells[22];
vector<ar<int, 2>> pf;
ll f[2*mxN+1], iF[2*mxN+1], ways[22][22], dp1[22], dp2[22][22];
vector<ar<int, 2>> ans_set;

ll bp(ll b, int p, int M) {
	ll r=1;
	for (; p; p/=2, b=b*b%M)
		if (p%2)
			r=r*b%M;
	return r;
}

ll C(int a, int b, ar<int, 2> prime, int pp) {
	assert(0<=b&&b<=a&&a<=n+m);
	int pwr=cnt[a]-cnt[b]-cnt[a-b];
	assert(pwr>=0);
	if (pwr>=prime[1])
		return 0;
	ll r=f[a]*iF[b]%pp*iF[a-b]%pp;
	while(pwr--)
		r=r*prime[0]%pp;
	return r;
}

bool ord(int i, int j) {
	return cells[i][0]<=cells[j][0]&&cells[i][1]<=cells[j][1];
}

void solve(ar<int, 2> prime) {
	int pp=1;
	for (int i=0; i<prime[1]; ++i)
		pp*=prime[0];
	f[0]=1, iF[0]=1;
	for (int i=1; i<=n+m; ++i) {
		int x=i;
		cnt[i]=cnt[i-1];
		while(x%prime[0]==0)
			x/=prime[0], ++cnt[i];
		f[i]=f[i-1]*x%pp;
		iF[i]=bp(f[i], pp/prime[0]*(prime[0]-1)-1, pp);
	}
	auto Go=[&](int i, int j) {
		assert(ord(i, j));
		int x=cells[j][0]-cells[i][0];
		int y=cells[j][1]-cells[i][1];
		return C(x+y, x, prime, pp);
	};
	for (int i=0; i<k+2; ++i)
		for (int j=i+1; j<k+2; ++j) {
			assert(cells[i]!=cells[j]&&cells[i][0]<=cells[j][0]);
			if (!ord(i, j)) {
				ways[i][j]=0;
				continue;
			}
			ways[i][j]=Go(i, j);
			for (int a=i+1; a<j; ++a) {
				if (ord(i, a)&&ord(a, j)) {
					dp1[a]=Go(i, a);
					for (int b=i+1; b<a; ++b)
						if (ord(i, b)&&ord(b, a))
							dp1[a]=(dp1[a]-dp1[b]*Go(b, a)%pp+pp)%pp;
					ways[i][j]=(ways[i][j]-dp1[a]*Go(a, j)%pp+pp)%pp;
				}
			}
		}
	memset(dp2, 0, sizeof(dp2));
	dp2[0][0]=1;
	for (int i=1; i<k+2; ++i)
		for (int j=1; j<k+2; ++j)
			for (int a=0; a<i; ++a)
				if (ord(a, i))
					dp2[i][j]=(dp2[i][j]+dp2[a][j-1]*ways[a][i])%pp;
	ll tot=0;
	for (int i=0; i<=t+1; ++i)
		tot=(tot+dp2[k+1][i])%pp;
	//cout << tot << " " << pp << endl;
	ans_set.push_back({(int)tot, pp});
}

ar<int, 2> mrg(ar<int, 2> a, ar<int, 2> b) {
	assert(a[1]<b[1]);
	ar<int, 2> c={b[0], a[1]*b[1]};
	for (int i=1; i<a[1]; ++i) {
		if (c[0]%a[1]==a[0])
			break;
		c[0]+=b[1];
	}
	assert(c[0]%a[1]==a[0]);
	return c;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k >> t >> z; // can hit <=t traps
	t=min(t, k);
	if (z==1) {
		cout << 0;
		return 0;
	}
	for (int i=2; i*i<=z; ++i) {
		if (z%i==0) {
			int c=0;
			while(z%i==0)
				z/=i, ++c;
			pf.push_back({i, c});
		}
	}
	if (z>1)
		pf.push_back({z, 1});
	for (int i=0; i<k; ++i)
		cin >> cells[i][0] >> cells[i][1];
	cells[k+1]={n, m};
	sort(cells, cells+k+2);
	for (ar<int, 2> prime : pf)
		solve(prime);
	sort(ans_set.begin(), ans_set.end(), [&](ar<int, 2> a, ar<int, 2> b) { return a[1]<b[1]; });
	while(ans_set.size()>1) {
		ar<int, 2> b=ans_set.back();
		ans_set.pop_back();
		ar<int, 2> a=ans_set.back();
		ans_set.pop_back();
		ans_set.push_back(mrg(a, b));
	}
	cout << ans_set[0][0];
	return 0;
}

• Subtask 1: 100 / 100