oj.uz

Submission #675918

# Submission time Handle Problem Language Result Execution time Memory
675918 2022-12-28T10:59:45 Z QwertyPi Energetic turtle (IZhO11_turtle) C++14
85 / 100
 327 ms 169444 KB 
#include <bits/stdc++.h>
#define int __int128_t
#define fi first
#define se second
using namespace std;

const int MAXN = 6e5 + 11;

int phi = 1;
map<int, int> pf;

map<int, int> f[MAXN]; 

int pm(int a, int b, int Z){
	if(b == 0) return 1;
	return pm(a * a % Z, b / 2, Z) * (b % 2 ? a : 1) % Z;
}

int mi(int a, int Z){
	a %= Z;
	return pm(a, phi - 1, Z);
} 

int C(int n, int r, int Z){
	if(n < r || r < 0) return 0;
	map<int, int> res; res[0] = 1;
	for(auto i : f[n]){
		if(i.fi == 0){
			res[0] = (res[0] * i.se) % Z;
		}else{
			res[i.fi] += i.se;
		}
	}
	for(auto i : f[r]){
		if(i.fi == 0){
			res[0] = (res[0] * mi(i.se, Z)) % Z;
		}else{
			res[i.fi] -= i.se;
		}
	}
	for(auto i : f[n - r]){
		if(i.fi == 0){
			res[0] = (res[0] * mi(i.se, Z)) % Z;
		}else{
			res[i.fi] -= i.se;
		}
	}
	int ans = 1;
	for(auto i : res){
		if(i.fi == 0){
			ans *= i.se;
			continue;
		}
		for(int j = 0; j < i.se; j++){
			ans *= i.fi; ans %= Z;
		}
	}
	return ans;
}

int p[25][2], d[25][25];
int Cu[25];

int32_t main(){
	int64_t N, M, K, T, Z;
	cin >> N >> M >> K >> T >> Z;
	phi = Z;
	int z = Z;
	for(int i = 2; i <= sqrt(1e9) + 11; i++){
		if(z % i == 0) phi = phi / i * (i - 1);
		while(z % i == 0) pf[i]++, z /= i;
	}
	if(z != 1) phi = phi / z * (z - 1), pf[z]++;
	
	f[0][0] = 1;
	for(int i = 1; i <= MAXN - 1; i++){
		f[i] = f[i - 1];
		int x = i;
		for(auto p : pf){
			while(x % p.fi == 0){
				f[i][p.fi]++; x /= p.fi;
			}
		}
		f[i][0] = f[i - 1][0] * x % Z;
	}
	
	p[0][0] = 0, p[0][1] = 0;
	p[K + 1][0] = N, p[K + 1][1] = M;
	
	vector<pair<int, int>> v;
	for(int i = 0; i < K; i++){
		int64_t x, y; cin >> x >> y;
		v.push_back({x, y});
	}
	sort(v.begin(), v.end());
	for(int i = 1; i <= K; i++){
		p[i][0] = v[i - 1].fi, p[i][1] = v[i - 1].se;
	}
	
	for(int i = 0; i <= K + 1; i++){
		for(int j = 0; j <= K + 1; j++){
			int dx = p[j][0] - p[i][0];
			int dy = p[j][1] - p[i][1];
			d[i][j] = C(dx + dy, dx, Z);
		}
	}
	
	for(int i = 0; i <= K; i++){
		Cu[i] = C(i, T + 1, Z);
	}
	
	int s = C(N + M, N, Z), t = 0;
	if(K <= T){
		cout << (long long) s << endl;
		return 0;
	}
	for(int i = 0; i < (1 << K); i++){
		int U = __builtin_popcount(i);
		int f = 1, pv = 0;
		for(int j = 0; j < K; j++){
			if(i & (1 << j)){
				f = f * d[pv][j + 1] % Z;
				pv = j + 1;
			}
		}
		f = f * d[pv][K + 1] % Z;
		t += ((U + T + 1) % 2 ? -1 : 1) * Cu[U] * f % Z;
		t %= Z;
	}
	cout << (long long)((s - t) % Z + Z) % Z << endl;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 169320 KB Output is correct
2 Incorrect 173 ms 169312 KB Output isn't correct
3 Correct 113 ms 121160 KB Output is correct
4 Correct 91 ms 98916 KB Output is correct
5 Correct 105 ms 121128 KB Output is correct
6 Incorrect 83 ms 99024 KB Output isn't correct
7 Correct 90 ms 99040 KB Output is correct
8 Correct 85 ms 98892 KB Output is correct
9 Correct 115 ms 98892 KB Output is correct
10 Correct 152 ms 98892 KB Output is correct
11 Correct 91 ms 99092 KB Output is correct
12 Correct 152 ms 98924 KB Output is correct
13 Correct 179 ms 169312 KB Output is correct
14 Correct 187 ms 169288 KB Output is correct
15 Correct 173 ms 169272 KB Output is correct
16 Correct 302 ms 169384 KB Output is correct
17 Incorrect 205 ms 169444 KB Output isn't correct
18 Correct 306 ms 169368 KB Output is correct
19 Correct 319 ms 169372 KB Output is correct
20 Correct 327 ms 169320 KB Output is correct