oj.uz

Submission #675933

# Submission time Handle Problem Language Result Execution time Memory
675933 2022-12-28T12:24:09 Z QwertyPi Energetic turtle (IZhO11_turtle) C++14
50 / 100
 298 ms 262144 KB 
#include <bits/stdc++.h>
#define int __int128_t
#define fi first
#define se second
using namespace std;

const int MAXN = 1e6 + 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
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 219 ms 262144 KB Execution killed with signal 9
2 Runtime error 218 ms 262144 KB Execution killed with signal 9
3 Correct 163 ms 202584 KB Output is correct
4 Correct 149 ms 180276 KB Output is correct
5 Correct 298 ms 202604 KB Output is correct
6 Correct 144 ms 180356 KB Output is correct
7 Correct 150 ms 180420 KB Output is correct
8 Correct 145 ms 180300 KB Output is correct
9 Correct 174 ms 180416 KB Output is correct
10 Correct 207 ms 180284 KB Output is correct
11 Correct 157 ms 180376 KB Output is correct
12 Correct 211 ms 180308 KB Output is correct
13 Runtime error 229 ms 262144 KB Execution killed with signal 9
14 Runtime error 224 ms 262144 KB Execution killed with signal 9
15 Runtime error 218 ms 262144 KB Execution killed with signal 9
16 Runtime error 222 ms 262144 KB Execution killed with signal 9
17 Runtime error 225 ms 262144 KB Execution killed with signal 9
18 Runtime error 220 ms 262144 KB Execution killed with signal 9
19 Runtime error 215 ms 262144 KB Execution killed with signal 9
20 Runtime error 216 ms 262144 KB Execution killed with signal 9