Submission #844838

#	Time	Username	Problem	Language	Result	Execution time	Memory
844838		AndriaBeridze	Energetic turtle (IZhO11_turtle)	C++14	5 / 100	1217 ms	44372 KiB

turtle

#include<bits/stdc++.h>

using namespace std;
int TC = 0;

void dbg_out() {cout << endl;}
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {cout << " " << H; dbg_out(T...);}
#define debug(...) {cout << "(" << #__VA_ARGS__ << "):"; dbg_out(__VA_ARGS__);}

#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define add push_back
#define size(v) (int) v.size()
#define left node * 2, l, (l + r) / 2
#define right node * 2 + 1, (l + r) / 2 + 1, r
#define check() cout << "Why doesn't this stupid a** code work?" << endl;
#define inf (int) 1e18

vector<int> dp(5000005, -1);
vector<int> x, y;
int n, m, k, t, z;

vector<int> f(300005, 0), f1(300005, 0);

long long pow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int C(int n, int k, int m){
    return f[n] * f1[n - k] % m * f1[k] % m;
}


int find(int i){
    if(dp[i] != -1){
        return dp[i];
    }
    int X = 0, Y = 0;
    for(int j = 0; j < 22; j++){
        if(i & (1 << j)){
            if(X > x[j]) dp[i] = 0;
            if(Y > y[j]) dp[i] = 0;
            X = x[j];
            Y = y[j];
        }
    }
    if(dp[i] != 0){
        if(__builtin_popcount(i) == 2){
            int l = -1, r = -1;
            for(int j = 0; j < 22; j++){
                if(i & (1 << j)){
                    if(l == -1) l = j;
                    r = j;
                }
            }
            dp[i] = C(abs(x[l] - x[r]) + abs(y[l] - y[r]), abs(x[l] - x[r]), z);
            int a = 0;
            for(int j = l; j <= r; j++){
                a += (1 << j);
            }
            for(int k = a; k; k = (k - 1) & a){
                if(!(k & (1 << l)) || !(k & (1 << r)) || i == k) continue;
                dp[i] -= find(k);
                dp[i] = (dp[i] + z) % z;
            }
        }
        else{
            vector<int> ind;
            for(int j = 0; j < 22; j++){
                if(i & (1 << j)) ind.push_back(j);
            }
            int a = 0, b = 0;
            for(int j = 0; j <= 1; j++) a += (1 << ind[j]);
            for(int j = 1; j < size(ind); j++) b += (1 << ind[j]);
            dp[i] = find(a) * find(b) % z;
        }
    }
    return dp[i];
}

void solve(){
    cin >> n >> m >> k >> t >> z;

    f[0] = f1[0] = 1;
    for(int i = 1; i <= 300000; i++){
        f[i] = f[i - 1] * i % (1000000007);
        f1[i] = f1[i - 1] * pow(i, 1000000005, 1000000007) % 1000000007;
    }

    vector<pair<int, int>> v = vector<pair<int,int>>(k + 2, {0, 0});
    x = y = vector<int>(k + 2, 0);
    for(int i = 1; i <= k; i++){
        cin >> x[i] >> y[i];
        v[i].first = x[i] + y[i];
        v[i].second = i;
    }

    x[0] = y[0] = 0;
    v[0].first = 0; v[0].second = 0;
    x[k + 1] = n, y[k + 1] = m;
    v[k + 1].first = n + m; v[k + 1].second = k + 1;

    sort(all(v));
    vector<int> a, b;
    for(int i = 0; i <= k + 1; i++){
        a.push_back(x[v[i].second]);
        b.push_back(y[v[i].second]);
    }
    x = a, y = b;

    for(int i = 0; i < (1 << (k + 2)); i++){
        if(__builtin_popcount(i) < 2) continue;
        dp[i] = find(i);
    }
    int ans = 0;
    int a1 = 0;
    for(int i = 0; i <= k + 1; i++){
        a1 += (1 << i);
    }
    for(int e = a1; e; e = (e - 1) & a1){
        if(__builtin_popcount(e) > t + 2 || !(e & 1) || !(e & (1 << (k + 1)))) continue;
        ans = (ans + dp[e]) % z;
    }
    cout << ans << endl;
}

signed main(){
    int q = 1;
    //cin >> q;
    while(++TC <= q){
    	solve();
    }
}

• Subtask 1: 5 / 100