Submission #844840

#	Time	Username	Problem	Language	Result	Execution time	Memory
844840		AndriaBeridze	Energetic turtle (IZhO11_turtle)	C++14	100 / 100	49 ms	13636 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:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |      for(int x = 0; x < primes.size(); x++) {
      |                     ~~^~~~~~~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:95:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |      scanf("%d%d%d%d%d", &N, &M, &K, &T, &Z);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:96:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |      for(i = 0; i < K; i++) scanf("%d%d", &D[i].x, &D[i].y);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100