Submission #4871

#	Time	Username	Problem	Language	Result	Execution time	Memory
4871		tncks0121	Energetic turtle (IZhO11_turtle)	C++98	100 / 100	137 ms	13584 KiB

turtle

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h> 
#include <time.h>

using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int SZ = 300005, K_ = 30;
int N, M, K, T, Z;

vector<int> primes;
bool sieve[SZ+SZ];

void getPrimes (int MX) {
	for(int p = 2; p <= MX; p++) {
		if(sieve[p]) continue;
		primes.push_back(p);
		for(int x = p+p; x <= MX; x += p) sieve[x] = true;
	}
}

ll power (ll a, ll b) {
	ll ret = 1;
	while(b > 0) {
		if(b & 1) ret = (ret * a) % Z;
		a = (a * a) % Z;
		b >>= 1;
	}
	return ret;
}

int nCr (int n, int r) {
	if(r == 0 || n == r) return 1;
	if(r == 1 || r == n-1) return n;

	ll ret = 1;
	for(int x = 0; x < primes.size(); x++) {
		int p = primes[x];
		if(p > n) break;
		ll v = 0;
		for(ll w = p; w <= n; w *= p) v += n / w;
		for(ll w = p; w <= r; w *= p) v -= r / w;
		for(ll w = p; w <= n-r; w *= p) v -= (n-r) / w;
		ret *= power(p, v);
		ret %= Z;
	}
	return ret % Z;
}

int ways (int x, int y) { // (x+y) C x
	return nCr (x+y, x);
}

struct point {
	int x, y;
	point(int x = 0, int y = 0): x(x), y(y) { }
	bool operator< (const point &p) const { return x != p.x ? x < p.x : y < p.y; }
} D[K_];

int F[K_], R[K_];
int W[K_][K_];

int Table[1<<20];
int LB[1<<20], CB[1<<20];
int Sum[K_];

ll res;

int main() {
	int i, j, k;

	scanf("%d%d%d%d%d", &N, &M, &K, &T, &Z);
	for(i = 0; i < K; i++) scanf("%d%d", &D[i].x, &D[i].y);

	if(K == 0) return 0 & printf("%d\n", ways(N, M));

	getPrimes(N+M);
	sort(D, D+K);

	for(i = 0; i < K; i++) {
		F[i] = ways(D[i].x, D[i].y);
		R[i] = ways(N - D[i].x, M - D[i].y);
		for(j = i+1; j < K; j++) {
			if(D[j].y >= D[i].y) W[i][j] = ways(D[j].x - D[i].x, D[j].y - D[i].y);
		}
	}

	Table[0] = 1;
	for(i = 0; i < K; i++) {
		Table[1<<i] = F[i];
		LB[1<<i] = i;
		CB[1<<i] = 1;
		for(int prev = 1; prev < (1<<i); prev++) {
			int now = prev | (1<<i);
			Table[now] = ((ll)Table[prev] * W[LB[prev]][i]) % Z;
			LB[now] = i;
			CB[now] = CB[prev] + 1;
		}
	}

	Table[0] = Sum[0] = ways(N, M);
	for(i = 1; i < (1<<K); i++) {
		Sum[CB[i]] += ((ll)Table[i] * R[LB[i]]) % Z;
		if(Sum[CB[i]] >= Z) Sum[CB[i]] -= Z;
	}

	for(k = 0; k <= T; k++) {
		int s = 1;
		for(i = k; i <= K; i++) {
			res += s * (((ll)Sum[i] * nCr(i, k)) % Z);
			if(res < 0) res += Z;
			res %= Z;
			s = -s;
		}
	}

	printf("%lld\n", res);

	return 0;
}

Compilation message (stderr)

turtle.cpp: In function 'int nCr(int, int)':
turtle.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x = 0; x < primes.size(); x++) {
                 ~~^~~~~~~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:95: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:96:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i = 0; i < K; i++) scanf("%d%d", &D[i].x, &D[i].y);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100