답안 #548167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
548167 2022-04-12T15:48:19 Z racsosabe 힘 센 거북 (IZhO11_turtle) C++14
100 / 100
266 ms 7344 KB
#include<bits/stdc++.h>
using namespace::std;

const int MAX = 600000 + 5;
const int N = 23;

int n;
int m;
int k;
int t;
int z;
int f[MAX];
int fi[MAX];
int pot[MAX];
int memo[N][N];
vector<pair<int, int>> v;

inline int mul(int a, int b, int MOD){
	return (1ll * a * b) % MOD;
}

int pow_mod(int a, int b, int MOD){
	int r = 1 % MOD;
	while(b){
		if(b & 1) r = mul(r, a, MOD);
		a = mul(a, a, MOD);
		b >>= 1;
	}
	return r;
}

void init(int p, int e, int mod){
	f[0] = 1;
	pot[0] = 0;
	for(int i = 1; i < MAX; i++){
		int x = i;
		pot[i] = pot[i - 1];
		while(x % p == 0){
			pot[i]++;
			x /= p;
		}
		f[i] = mul(x, f[i - 1], mod);
	}
	fi[MAX - 1] = pow_mod(f[MAX - 1], mod - mod / p - 1, mod);
	for(int i = MAX - 2; i >= 0; i--){
		int x = i + 1;
		while(x % p == 0) x /= p;
		fi[i] = mul(x, fi[i + 1], mod);
	}
}

int C(int a, int b, int p, int e, int mod){
	if(a < b) return 0;
	if(pot[a] - pot[b] - pot[a - b] >= e) return 0;
	return mul(pow_mod(p, pot[a] - pot[b] - pot[a - b], mod), mul(f[a], mul(fi[b], fi[a - b], mod), mod), mod);
}

void preprocess(int p, int e, int mod){
	for(int i = 0; i < v.size(); i++){
		for(int j = i; j < v.size(); j++){
			if(v[i].second > v[j].second) continue;
			int dx = v[j].first - v[i].first;
			int dy = v[j].second - v[i].second;
			memo[i][j] = C(dx + dy, dx, p, e, mod);
			for(int k = i + 1; k < j; k++){
				if(v[i].second > v[k].second or v[k].second > v[j].second) continue;
				memo[i][j] += mod - mul(memo[i][k], C(v[j].first - v[k].first + v[j].second - v[k].second, v[j].first - v[k].first, p, e, mod), mod);
				if(memo[i][j] >= mod) memo[i][j] -= mod;
			}
		}
	}
}

typedef long long ll;

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (b) { ll d = euclid(b, a % b, y, x);
		return y -= a/b * x, d; }
	return x = 1, y = 0, a;
}

ll crt(ll a, ll m, ll b, ll n) {
	if (n > m) swap(a, b), swap(m, n);
	ll x, y, g = euclid(m, n, x, y);
	assert((a - b) % g == 0); // else no solution
	x = (b - a) % n * x % n / g * m + a;
	return x < 0 ? x + m*n/g : x;
}

ll crt(vector<pair<int, int>> &v){
	while(v.size() > 1){
		pair<int, int> p1 = v.back(); v.pop_back();
		pair<int, int> p2 = v.back(); v.pop_back();
		int m = crt(p1.first, p1.second, p2.first, p2.second);
		v.emplace_back(make_pair(m, p1.second * p2.second));
	}
	return v.back().first;
}

int compute(int p, int e, int mod){
	init(p, e, mod);
	preprocess(p, e, mod);
	int ans = 0;
	for(int mask = 0; mask < (1 << k); mask++){
		if(__builtin_popcount(mask) > t) continue;
		int last = 0;
		int res = 1;
		for(int i = 0, p = 1; i < k; i++, p <<= 1){
			if(mask & p){
				res = mul(res, memo[last][i + 1], mod);
				last = i + 1;
			}
		}
		res = mul(res, memo[last][v.size() - 1], mod);
		ans += res;
		if(ans >= mod) ans -= mod;
	}
	return ans;
}

int solve(){
	if(z == 1) return 0;
	vector<pair<int, int>> mods;
	for(int i = 2; i * i <= z; i++){
		if(z % i == 0){
			int p = i;
			int e = 0;
			int val = 1;
			while(z % i == 0){
				val *= i;
				z /= i;
				e++;
			}
			mods.emplace_back(make_pair(compute(p, e, val), val));
		}
	}
	if(z > 1){
		mods.emplace_back(make_pair(compute(z, 1, z), z));
	}
	return crt(mods);
}

int main(){
	scanf("%d %d %d %d %d", &n, &m, &k, &t, &z);
	v.emplace_back(make_pair(0, 0));
	for(int i = 0; i < k; i++){
		int x, y;
		scanf("%d %d", &x, &y);
		v.emplace_back(make_pair(x, y));
	}
	v.emplace_back(make_pair(n, m));
	sort(v.begin(), v.end());
	printf("%d\n", solve());
	return 0;
}

Compilation message

turtle.cpp: In function 'void preprocess(int, int, int)':
turtle.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
turtle.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(int j = i; j < v.size(); j++){
      |                  ~~^~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%d %d %d %d %d", &n, &m, &k, &t, &z);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 7332 KB Output is correct
2 Correct 69 ms 7320 KB Output is correct
3 Correct 22 ms 7244 KB Output is correct
4 Correct 25 ms 7252 KB Output is correct
5 Correct 118 ms 7332 KB Output is correct
6 Correct 22 ms 7344 KB Output is correct
7 Correct 26 ms 7228 KB Output is correct
8 Correct 21 ms 7256 KB Output is correct
9 Correct 29 ms 7336 KB Output is correct
10 Correct 36 ms 7244 KB Output is correct
11 Correct 25 ms 7252 KB Output is correct
12 Correct 59 ms 7336 KB Output is correct
13 Correct 70 ms 7244 KB Output is correct
14 Correct 88 ms 7336 KB Output is correct
15 Correct 256 ms 7232 KB Output is correct
16 Correct 79 ms 7296 KB Output is correct
17 Correct 75 ms 7336 KB Output is correct
18 Correct 80 ms 7332 KB Output is correct
19 Correct 119 ms 7340 KB Output is correct
20 Correct 266 ms 7340 KB Output is correct