oj.uz

Submission #881977

# Submission time Handle Problem Language Result Execution time Memory
881977 2023-12-02T11:12:56 Z dosts Energetic turtle (IZhO11_turtle) C++17
5 / 100
 2000 ms 13788 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=6e5+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 3 ms 5600 KB Output is correct
2 Incorrect 3 ms 5600 KB Output isn't correct
3 Incorrect 3 ms 5600 KB Output isn't correct
4 Incorrect 69 ms 5780 KB Output isn't correct
5 Execution timed out 2065 ms 13788 KB Time limit exceeded
6 Incorrect 20 ms 5596 KB Output isn't correct
7 Incorrect 712 ms 6168 KB Output isn't correct
8 Incorrect 17 ms 5600 KB Output isn't correct
9 Execution timed out 2056 ms 7896 KB Time limit exceeded
10 Execution timed out 2015 ms 9688 KB Time limit exceeded
11 Execution timed out 2033 ms 6104 KB Time limit exceeded
12 Execution timed out 2021 ms 9688 KB Time limit exceeded
13 Execution timed out 2035 ms 5596 KB Time limit exceeded
14 Execution timed out 2065 ms 6620 KB Time limit exceeded
15 Execution timed out 2055 ms 13788 KB Time limit exceeded
16 Execution timed out 2067 ms 13788 KB Time limit exceeded
17 Execution timed out 2069 ms 7644 KB Time limit exceeded
18 Execution timed out 2023 ms 13784 KB Time limit exceeded
19 Execution timed out 2094 ms 13784 KB Time limit exceeded
20 Execution timed out 2049 ms 13788 KB Time limit exceeded