oj.uz

Submission #675932

# Submission time Handle Problem Language Result Execution time Memory
675932 2022-12-28T12:22:58 Z QwertyPi Energetic turtle (IZhO11_turtle) C++14
50 / 100
 293 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) 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 213 ms 262144 KB Execution killed with signal 9
2 Runtime error 210 ms 262144 KB Execution killed with signal 9
3 Correct 169 ms 202608 KB Output is correct
4 Correct 147 ms 180300 KB Output is correct
5 Correct 293 ms 202572 KB Output is correct
6 Correct 149 ms 180464 KB Output is correct
7 Correct 152 ms 180444 KB Output is correct
8 Correct 142 ms 180312 KB Output is correct
9 Correct 175 ms 180344 KB Output is correct
10 Correct 211 ms 180236 KB Output is correct
11 Correct 151 ms 180428 KB Output is correct
12 Correct 210 ms 180300 KB Output is correct
13 Runtime error 214 ms 262144 KB Execution killed with signal 9
14 Runtime error 217 ms 262144 KB Execution killed with signal 9
15 Runtime error 216 ms 262144 KB Execution killed with signal 9
16 Runtime error 222 ms 262144 KB Execution killed with signal 9
17 Runtime error 222 ms 262144 KB Execution killed with signal 9
18 Runtime error 213 ms 262144 KB Execution killed with signal 9
19 Runtime error 213 ms 262144 KB Execution killed with signal 9
20 Runtime error 216 ms 262144 KB Execution killed with signal 9