Submission #548167

#	Time	Username	Problem	Language	Result	Execution time	Memory
548167		racsosabe	Energetic turtle (IZhO11_turtle)	C++14	100 / 100	266 ms	7344 KiB

turtle

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

const int MAX = 600000 + 5;
const int N = 23;

int n;
int m;
int k;
int t;
int z;
int f[MAX];
int fi[MAX];
int pot[MAX];
int memo[N][N];
vector<pair<int, int>> v;

inline int mul(int a, int b, int MOD){
	return (1ll * a * b) % MOD;
}

int pow_mod(int a, int b, int MOD){
	int r = 1 % MOD;
	while(b){
		if(b & 1) r = mul(r, a, MOD);
		a = mul(a, a, MOD);
		b >>= 1;
	}
	return r;
}

void init(int p, int e, int mod){
	f[0] = 1;
	pot[0] = 0;
	for(int i = 1; i < MAX; i++){
		int x = i;
		pot[i] = pot[i - 1];
		while(x % p == 0){
			pot[i]++;
			x /= p;
		}
		f[i] = mul(x, f[i - 1], mod);
	}
	fi[MAX - 1] = pow_mod(f[MAX - 1], mod - mod / p - 1, mod);
	for(int i = MAX - 2; i >= 0; i--){
		int x = i + 1;
		while(x % p == 0) x /= p;
		fi[i] = mul(x, fi[i + 1], mod);
	}
}

int C(int a, int b, int p, int e, int mod){
	if(a < b) return 0;
	if(pot[a] - pot[b] - pot[a - b] >= e) return 0;
	return mul(pow_mod(p, pot[a] - pot[b] - pot[a - b], mod), mul(f[a], mul(fi[b], fi[a - b], mod), mod), mod);
}

void preprocess(int p, int e, int mod){
	for(int i = 0; i < v.size(); i++){
		for(int j = i; j < v.size(); j++){
			if(v[i].second > v[j].second) continue;
			int dx = v[j].first - v[i].first;
			int dy = v[j].second - v[i].second;
			memo[i][j] = C(dx + dy, dx, p, e, mod);
			for(int k = i + 1; k < j; k++){
				if(v[i].second > v[k].second or v[k].second > v[j].second) continue;
				memo[i][j] += mod - mul(memo[i][k], C(v[j].first - v[k].first + v[j].second - v[k].second, v[j].first - v[k].first, p, e, mod), mod);
				if(memo[i][j] >= mod) memo[i][j] -= mod;
			}
		}
	}
}

typedef long long ll;

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (b) { ll d = euclid(b, a % b, y, x);
		return y -= a/b * x, d; }
	return x = 1, y = 0, a;
}

ll crt(ll a, ll m, ll b, ll n) {
	if (n > m) swap(a, b), swap(m, n);
	ll x, y, g = euclid(m, n, x, y);
	assert((a - b) % g == 0); // else no solution
	x = (b - a) % n * x % n / g * m + a;
	return x < 0 ? x + m*n/g : x;
}

ll crt(vector<pair<int, int>> &v){
	while(v.size() > 1){
		pair<int, int> p1 = v.back(); v.pop_back();
		pair<int, int> p2 = v.back(); v.pop_back();
		int m = crt(p1.first, p1.second, p2.first, p2.second);
		v.emplace_back(make_pair(m, p1.second * p2.second));
	}
	return v.back().first;
}

int compute(int p, int e, int mod){
	init(p, e, mod);
	preprocess(p, e, mod);
	int ans = 0;
	for(int mask = 0; mask < (1 << k); mask++){
		if(__builtin_popcount(mask) > t) continue;
		int last = 0;
		int res = 1;
		for(int i = 0, p = 1; i < k; i++, p <<= 1){
			if(mask & p){
				res = mul(res, memo[last][i + 1], mod);
				last = i + 1;
			}
		}
		res = mul(res, memo[last][v.size() - 1], mod);
		ans += res;
		if(ans >= mod) ans -= mod;
	}
	return ans;
}

int solve(){
	if(z == 1) return 0;
	vector<pair<int, int>> mods;
	for(int i = 2; i * i <= z; i++){
		if(z % i == 0){
			int p = i;
			int e = 0;
			int val = 1;
			while(z % i == 0){
				val *= i;
				z /= i;
				e++;
			}
			mods.emplace_back(make_pair(compute(p, e, val), val));
		}
	}
	if(z > 1){
		mods.emplace_back(make_pair(compute(z, 1, z), z));
	}
	return crt(mods);
}

int main(){
	scanf("%d %d %d %d %d", &n, &m, &k, &t, &z);
	v.emplace_back(make_pair(0, 0));
	for(int i = 0; i < k; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		v.emplace_back(make_pair(x, y));
	}
	v.emplace_back(make_pair(n, m));
	sort(v.begin(), v.end());
	printf("%d\n", solve());
	return 0;
}

Compilation message (stderr)

turtle.cpp: In function 'void preprocess(int, int, int)':
turtle.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
turtle.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int j = i; j < v.size(); j++){
      |                  ~~^~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%d %d %d %d %d", &n, &m, &k, &t, &z);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100