oj.uz

Submission #675910

# Submission time Handle Problem Language Result Execution time Memory
675910 2022-12-28T10:41:43 Z QwertyPi Energetic turtle (IZhO11_turtle) C++14
85 / 100
 328 ms 169436 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[22][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;
	for(int i = 0; i < (1 << K); i++){
		int U = __builtin_popcount(i);
		if(U >= T + 1){
			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 161 ms 169280 KB Output is correct
2 Incorrect 162 ms 169356 KB Output isn't correct
3 Correct 106 ms 121164 KB Output is correct
4 Correct 83 ms 98852 KB Output is correct
5 Correct 119 ms 121152 KB Output is correct
6 Incorrect 81 ms 98976 KB Output isn't correct
7 Correct 82 ms 99036 KB Output is correct
8 Correct 81 ms 98832 KB Output is correct
9 Correct 106 ms 98892 KB Output is correct
10 Correct 128 ms 98876 KB Output is correct
11 Correct 83 ms 99084 KB Output is correct
12 Correct 96 ms 98892 KB Output is correct
13 Correct 167 ms 169428 KB Output is correct
14 Correct 170 ms 169292 KB Output is correct
15 Correct 176 ms 169292 KB Output is correct
16 Correct 308 ms 169436 KB Output is correct
17 Incorrect 196 ms 169344 KB Output isn't correct
18 Correct 328 ms 169348 KB Output is correct
19 Correct 277 ms 169292 KB Output is correct
20 Correct 170 ms 169376 KB Output is correct