oj.uz

Submission #675934

# Submission time Handle Problem Language Result Execution time Memory
675934 2022-12-28T12:24:42 Z QwertyPi Energetic turtle (IZhO11_turtle) C++14
15 / 100
 206 ms 113032 KB 
#include <bits/stdc++.h>
#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){
	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
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 112896 KB Output is correct
2 Incorrect 140 ms 113000 KB Output isn't correct
3 Correct 85 ms 83976 KB Output is correct
4 Incorrect 72 ms 70680 KB Output isn't correct
5 Correct 154 ms 84104 KB Output is correct
6 Incorrect 69 ms 70732 KB Output isn't correct
7 Incorrect 73 ms 70708 KB Output isn't correct
8 Incorrect 69 ms 70680 KB Output isn't correct
9 Incorrect 86 ms 70728 KB Output isn't correct
10 Incorrect 105 ms 70688 KB Output isn't correct
11 Incorrect 74 ms 70736 KB Output isn't correct
12 Incorrect 104 ms 70616 KB Output isn't correct
13 Incorrect 137 ms 112944 KB Output isn't correct
14 Incorrect 143 ms 112972 KB Output isn't correct
15 Incorrect 206 ms 112884 KB Output isn't correct
16 Incorrect 202 ms 112924 KB Output isn't correct
17 Incorrect 153 ms 113008 KB Output isn't correct
18 Incorrect 205 ms 112956 KB Output isn't correct
19 Incorrect 203 ms 113000 KB Output isn't correct
20 Incorrect 205 ms 113032 KB Output isn't correct