oj.uz

Submission #881976

# Submission time Handle Problem Language Result Execution time Memory
881976 2023-12-02T11:08:28 Z dosts Energetic turtle (IZhO11_turtle) C++14
5 / 100
 2000 ms 10468 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 1e5+1,inf = 1e18,P=2e5+1;
int MOD;
vi pri;
int sieve[P];
int add(int x,int y) {return (x+y >= MOD)?x+y-MOD:x+y;}
int mult(int x,int y) {return ((x%MOD)*(y%MOD))%MOD;}
int expo(int x,int y) {
  if (!y) return 1;
  int e = expo(x,y/2);
  e = mult(e,e);
  if (y&1) e = mult(e,x);
  return e;
}
void prec() {
  memset(sieve,0,sizeof sieve);
  for (int i=2;i<P;i++) {
    if (!sieve[i]){
      sieve[i] = i;
      pri.push_back(i);
      for (int j=i*i;j<P;j+=i) sieve[j] = i; 
    }
  }
}
int nck(int n,int k) {
  if (n<k) return 0;
  if (n<0 || k < 0) return 0;
  int ans = 1;
  for (auto it : pri) {
    if (it > n) break;
    int sm = 0;
    for (int cur = it;cur<=n;cur*=it) sm+=n/cur;
    for (int cur = it;cur<=k;cur*=it) sm-=k/cur;
    for (int cur = it;cur<=n-k;cur*=it) sm-=(n-k)/cur;
    ans = mult(ans,expo(it,sm));
  }
  return ans;
}

void solve() {
  int n,m,k,t;
  cin >> n >> m >> k >> t >> MOD;
  prec();
  n++;
  m++;
  vector<pii> pts(k+1);
  F(i,k) cin >> pts[i].first >> pts[i].second;
  F(i,k) pts[i].first++;
  F(i,k) pts[i].second++;
  sort(pts.begin()+1,pts.end());
  int lim = (1<<k);
  vi dp(lim,0);
  for (int i=0;i<lim;i++) {
    vi ys;
    vector<pii> pt = {{1,1}};
    for (int j=0;j<k;j++) if (i&(1<<j)) pt.push_back(pts[j+1]);
    pt.push_back({n,m});
    int sz = pt.size();
    int p = 1;
    for (int i=0;i<sz-1;i++) {
      int dx = pt[i+1].first-pt[i].first;
      int dy = pt[i+1].second-pt[i].second;
      p = mult(p,nck(dx+dy,dx));
    }
    dp[i] = p;
  }
  int ans = 0;
  for (int i=0;i<lim;i++) {
    int pc = __builtin_popcountll(i);
    if (pc > t && pc%2!=t%2) {
      ans = add(ans,MOD-dp[i]);
    }
    else ans = add(ans,dp[i]);
  }
  cout << ans << endl;
}	
    
                  
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout);
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 2 ms 2396 KB Output isn't correct
4 Incorrect 68 ms 2548 KB Output isn't correct
5 Execution timed out 2048 ms 10464 KB Time limit exceeded
6 Incorrect 18 ms 2396 KB Output isn't correct
7 Incorrect 712 ms 2800 KB Output isn't correct
8 Incorrect 16 ms 2396 KB Output isn't correct
9 Execution timed out 2083 ms 4148 KB Time limit exceeded
10 Execution timed out 2025 ms 6364 KB Time limit exceeded
11 Execution timed out 2061 ms 2784 KB Time limit exceeded
12 Execution timed out 2021 ms 6364 KB Time limit exceeded
13 Incorrect 1635 ms 2396 KB Output isn't correct
14 Execution timed out 2054 ms 3296 KB Time limit exceeded
15 Execution timed out 2053 ms 10464 KB Time limit exceeded
16 Execution timed out 2041 ms 10460 KB Time limit exceeded
17 Execution timed out 2037 ms 4316 KB Time limit exceeded
18 Execution timed out 2025 ms 10464 KB Time limit exceeded
19 Execution timed out 2053 ms 10464 KB Time limit exceeded
20 Execution timed out 2067 ms 10468 KB Time limit exceeded