제출 #683351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683351		vovamr	힘 센 거북 (IZhO11_turtle)	C++17	100 / 100	285 ms	23332 KiB

turtle

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

const int N = 6e5 + 100;

int md;
inline int add(int a, int b) { if ((a += b) >= md) a -= md; return a; }
inline void ads(int &a, int b) { if ((a += b) >= md) a -= md; }
inline int sub(int a, int b) { if ((a -= b) < 0) a += md; return a; }
inline void subs(int &a, int b) { if ((a -= b) < 0) a += md; }
inline int mul(int a, int b) { return a * 1ll * b % md; }
inline void muls(int &a, int b) { a = a * 1ll * b % md; }
inline int bp(int a, int n) { int res = 1;
	for (; n; n >>= 1, muls(a, a)) {
		if (n & 1) muls(res, a);
	} return res;
}

int lp[N];
ve<int> pr;

int pw[N][20];

inline void calc() {
	for (int i = 2; i < N; ++i) {
		if (!lp[i]) lp[i] = i, pr.pb(i);
		for (int j = 0; j < sz(pr) && i * pr[j] < N && pr[j] <= lp[i]; ++j) {
			lp[i * pr[j]] = pr[j];
		}
	}

	for (int id = 0; id < sz(pr); ++id) {
		const int &p = pr[id];

		pw[id][0] = 1;
		for (int i = 1; i < 20; ++i) pw[id][i] = mul(pw[id][i - 1], p);
	}
}

inline int c(int n, int k) {
	int answer = 1;
	int cnt; ll f; int nk = n - k;
	for (int id = 0; id < sz(pr) && pr[id] <= n; ++id) {
		const int &p = pr[id]; cnt = 0;

		f = p;
		while (f <= n) cnt += n / f, f *= p;

		f = p;
		while (f <= k) cnt -= k / f, f *= p;

		f = p;
		while (f <= nk) cnt -= nk / f, f *= p;
		
		muls(answer, pw[id][cnt]);
	}
	return answer;
}

inline void solve() {

	int n, m, k, t;
	cin >> n >> m >> k >> t >> md;

	calc();

	ve<pii> pts(k);
	for (auto &[x, y] : pts) cin >> x >> y;

	pts.pb({0, 0}); pts.pb({n, m});

	sort(all(pts), [](const pii &a, const pii &b) {
		return a.fi + a.se < b.fi + b.se;
	});

	int s = sz(pts);
	ve<ve<int>> cost(s, ve<int> (s));

	for (int i = 0; i < s; ++i) {
		const auto &[x1, y1] = pts[i];
		for (int j = i + 1; j < s; ++j) {
			const auto [x2, y2] = pts[j];

			if (!(x2 >= x1 && y2 >= y1)) continue;
			cost[i][j] = c(x2 - x1 + y2 - y1, x2 - x1);
		}
	}

	ve<int> value(1 << s);
	for (int mask = 0; mask < (1 << s); ++mask) {
		if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;

		int prev = 0, result = 1;
		for (int i = 1; i < s; ++i) {
			if (mask >> i & 1 ^ 1) continue;

			muls(result, cost[prev][i]);
			prev = i;
		}
		value[mask] = result;
	}
	for (int i = 0; i < (1 << s); ++i) if (__builtin_popcount(i) & 1) {
		value[i] = md - value[i];
	}

	for (int i = 0; i < s; ++i) {
		for (int ma = 0; ma < (1 << s); ++ma) {
			if (ma >> i & 1) continue;
			ads(value[ma], value[ma ^ (1 << i)]);
		}
	}
	for (int i = 0; i < (1 << s); ++i) if (__builtin_popcount(i) & 1) {
		value[i] = md - value[i];
	}

	int answer = 0;
	for (int mask = 0; mask < (1 << s); ++mask) {
		if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
		if (__builtin_popcount(mask) - 2 <= t) {
			ads(answer, value[mask]);
		}
	}

	cout << answer;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

turtle.cpp: In function 'void solve()':
turtle.cpp:110:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  110 |   if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
      |        ~~~~~~~~~~^~~
turtle.cpp:110:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  110 |   if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
      |                               ~~~~~~~~~~~~~~~~^~~
turtle.cpp:114:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  114 |    if (mask >> i & 1 ^ 1) continue;
      |        ~~~~~~~~~~^~~
turtle.cpp:137:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  137 |   if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
      |        ~~~~~~~~~~^~~
turtle.cpp:137:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  137 |   if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
      |                               ~~~~~~~~~~~~~~~~^~~

• Subtask 1: 100 / 100