Submission #17745

#	Time	Username	Problem	Language	Result	Execution time	Memory
17745		chrome	Energetic turtle (IZhO11_turtle)	C++98	15 / 100	1252 ms	262144 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) {
	if (~v & 1) return false;
	for (int i = 3; i * i <= v; i += 2)
		if (v % i == 0)
			return false;
	return true;
}

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

	int n, m, k, t, z; 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);
	}
	
	if (prime(z)) {
		cout << get(n + m, n, z);
	} else {
		for (int i = 1; i <= n + m; ++i) {
			c[i][0] = c[i][i] = 1;
			for (int j = 1; j < i; ++j) {
				c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % z;
			}
		}
		cout << c[n + m][n];
	}
	
	return 0;
}

Compilation message (stderr)

turtle.cpp: In function 'int main()':
turtle.cpp:63:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, m, k, t, z; scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:66: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: 15 / 100