Submission #17772

#	Time	Username	Problem	Language	Result	Execution time	Memory
17772		chrome	Energetic turtle (IZhO11_turtle)	C++98	40 / 100	268 ms	123896 KiB

turtle

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define foreach(it, S) for (__typeof (S.begin()) it = S.begin(); it != S.end(); it++)
#define all(x) x.begin(), x.end()
#define endl '\n'
#define _ ios_base :: sync_with_stdio(false); cin.tie(NULL);

#ifdef inputf
	#define fname ""
#else
	#define fname "" // <- Here
#endif

const double eps = 1e-9;
const int MaxN = int(2e5) + 256;
const int MOD = int(1e9) + 7;

template <typename T> inline T gcd(T a, T b) {
	return b ? gcd (b, a % b) : a;
}

inline bool Palindrome(const string& s) {
	return equal(s.begin(), s.end(), s.rbegin());
}

int d[21][1200][1200];
int f[10 * MaxN], inv[10 * MaxN];
int a[1200][1200];
int c[5000][5000];

inline int binpow(int a, int n, int z) {
	int res = 1;
	while (n) {
		if (n & 1)
			res = (res * 1ll * a) % z;
		a = (a * 1ll * a) % z;
		n >>= 1;
	}
	return res;
}

inline int get(int n, int k, int z) {
	return f[n] * inv[k] % z * inv[n - k] % z; 
}

inline bool prime(int v) {
	for (int i = 2; i * i <= v; ++i)
		if (v % i == 0)
			return false;
	return true;
}

int n, m, k, t, z;

int gcd(int a, int b, int & x, int & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	int x1, y1;
	int d = gcd(b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

int q(int cnt, int x, int y) {
	if (cnt > t || x > n || y > m)
		return 0;
	if (x == n && y == m)
		return 1;
	int &res = d[cnt][x][y];
	if (~res)
		return res;
	res = 0;
	if (a[x][y])
		++cnt;
	res = (q(cnt, x + 1, y) + q(cnt, x, y + 1)) % z;
	return res;
}

int main() { // _
	#ifdef lcl
		freopen(fname".in", "r", stdin);
		freopen(fname".out", "w", stdout);
	#endif

	scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);

	for (int i = 0; i < k; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		a[x][y] = 1;
	}

	f[0] = inv[0] = 1;
	
	for (int i = 1; i <= n + m; ++i) {
		f[i] = f[i - 1] * 1ll * i % z;
		// inv[i] = binpow(f[i], z - 2, z);
		int x = 0, y = 0;
		int g = gcd(f[i], z, x, y);
		x = (x % z + z) % z;
		inv[i] = x;
	}
	
	if (!k) {
		cout << get(n + m, n, z);
		return 0;
	}

	memset(d, 255, sizeof d);
	cout << q(0, 0, 0);
	
	return 0;
}

Compilation message (stderr)

turtle.cpp: In function 'int main()':
turtle.cpp:104:7: warning: unused variable 'g' [-Wunused-variable]
   int g = gcd(f[i], z, x, y);
       ^
turtle.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100