oj.uz

Submission #881974

# Submission time Handle Problem Language Result Execution time Memory
881974 2023-12-02T11:06:51 Z dosts Energetic turtle (IZhO11_turtle) C++17
5 / 100
 2000 ms 93916 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=1e7+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 142 ms 87020 KB Output is correct
2 Incorrect 124 ms 87300 KB Output isn't correct
3 Incorrect 123 ms 87020 KB Output isn't correct
4 Incorrect 180 ms 88296 KB Output isn't correct
5 Execution timed out 2021 ms 92352 KB Time limit exceeded
6 Incorrect 132 ms 88520 KB Output isn't correct
7 Incorrect 817 ms 87240 KB Output isn't correct
8 Incorrect 129 ms 87292 KB Output isn't correct
9 Execution timed out 2032 ms 87752 KB Time limit exceeded
10 Execution timed out 2048 ms 89032 KB Time limit exceeded
11 Execution timed out 2013 ms 87232 KB Time limit exceeded
12 Execution timed out 2054 ms 89064 KB Time limit exceeded
13 Execution timed out 2028 ms 87548 KB Time limit exceeded
14 Execution timed out 2025 ms 88260 KB Time limit exceeded
15 Execution timed out 2051 ms 93916 KB Time limit exceeded
16 Execution timed out 2027 ms 93628 KB Time limit exceeded
17 Execution timed out 2003 ms 86980 KB Time limit exceeded
18 Execution timed out 2012 ms 93420 KB Time limit exceeded
19 Execution timed out 2031 ms 93628 KB Time limit exceeded
20 Execution timed out 2023 ms 92348 KB Time limit exceeded