oj.uz

Submission #675935

# Submission time Handle Problem Language Result Execution time Memory
675935 2022-12-28T12:25:12 Z QwertyPi Energetic turtle (IZhO11_turtle) C++14
100 / 100
 257 ms 141260 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
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){
	a %= 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 || n < 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; ans %= Z;
			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 = i + 1; j <= K + 1; j++){
			int dx = p[j][0] - p[i][0];
			int dy = p[j][1] - p[i][1];
			if(dx >= 0 && dy >= 0) d[i][j] = C(dx + dy, dx, Z);
		}
	}
	
	for(int i = 0; i <= K; i++){
		Cu[i] = C(i - 1, T, Z);
	}
	
	int s = C(N + M, N, Z), t = 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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 141136 KB Output is correct
2 Correct 142 ms 141084 KB Output is correct
3 Correct 83 ms 102608 KB Output is correct
4 Correct 76 ms 84744 KB Output is correct
5 Correct 156 ms 102604 KB Output is correct
6 Correct 69 ms 84832 KB Output is correct
7 Correct 84 ms 84904 KB Output is correct
8 Correct 71 ms 84816 KB Output is correct
9 Correct 87 ms 84840 KB Output is correct
10 Correct 102 ms 84748 KB Output is correct
11 Correct 72 ms 84904 KB Output is correct
12 Correct 104 ms 84828 KB Output is correct
13 Correct 158 ms 141144 KB Output is correct
14 Correct 157 ms 141192 KB Output is correct
15 Correct 222 ms 141136 KB Output is correct
16 Correct 235 ms 141108 KB Output is correct
17 Correct 178 ms 141084 KB Output is correct
18 Correct 249 ms 141260 KB Output is correct
19 Correct 257 ms 141144 KB Output is correct
20 Correct 241 ms 141160 KB Output is correct