oj.uz

Submission #675869

# Submission time Handle Problem Language Result Execution time Memory
675869 2022-12-28T09:04:27 Z QwertyPi Energetic turtle (IZhO11_turtle) C++14
85 / 100
 234 ms 141196 KB 
#include <bits/stdc++.h>
#define int long long
#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[22][2], d[22][22];
int Cu[22];

int32_t main(){
	int N, M, K, T, Z;
	cin >> N >> M >> K >> T >> Z; 
	if(Z == 0){
		cout << 0 << endl;
		return 0;
	}
	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++){
		int 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;
		}
	}
	cout << ((s - t) % Z + Z) % Z << endl;
}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 141172 KB Output is correct
2 Incorrect 148 ms 141148 KB Output isn't correct
3 Correct 88 ms 102556 KB Output is correct
4 Correct 71 ms 84800 KB Output is correct
5 Correct 112 ms 102740 KB Output is correct
6 Incorrect 68 ms 84900 KB Output isn't correct
7 Correct 71 ms 84824 KB Output is correct
8 Correct 73 ms 84756 KB Output is correct
9 Correct 97 ms 84864 KB Output is correct
10 Correct 104 ms 84812 KB Output is correct
11 Correct 71 ms 84924 KB Output is correct
12 Correct 76 ms 84840 KB Output is correct
13 Correct 146 ms 141084 KB Output is correct
14 Correct 150 ms 141104 KB Output is correct
15 Correct 157 ms 141136 KB Output is correct
16 Correct 224 ms 141180 KB Output is correct
17 Incorrect 167 ms 141196 KB Output isn't correct
18 Correct 234 ms 141188 KB Output is correct
19 Correct 234 ms 141192 KB Output is correct
20 Correct 160 ms 141072 KB Output is correct