Submission #52088

#	Time	Username	Problem	Language	Result	Execution time	Memory
52088		FLDutchman	Energetic turtle (IZhO11_turtle)	C++14	100 / 100	160 ms	1780 KiB

turtle

#include "bits/stdc++.h"
using namespace std;

#define fast_io() ios::sync_with_stdio(false)
#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define snd second
#define fst first
#define pb push_back

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int NMAX = 300100;

int N, M, K, T, Z;
vi primes;
vii traps;
vi adj[30];

int mod(int n){
    if(n >= 0) return n % Z;
    else return (n%Z) + Z;
}


int expcnt(int n, int p){
    int res = 0;
    while(n){
        n/= p;
        res += n;
    }
    return res;
}

int mpow(int a, int b){
    if(b == 0) return 1;
    if(b & 1) return a*mpow(a*a%Z, b>>1)%Z;
    return mpow(a*a%Z, b>>1); 
}

int C(int a, int b){
    // a! / (b!(a-b)!)
    int res = 1;
    for(int i = 0; primes[i] <= a; i++){
        int ex = expcnt(a, primes[i]) - expcnt(b, primes[i]) - expcnt(a-b, primes[i]);
        res = mod(res * mpow(primes[i], ex));
    }
    return res;
}

int dp3[30][30];

int ways(int a, int b){
    int &res = dp3[a][b];
    if(res != -1) return res;
    int dx = traps[a].fst - traps[b].fst, dy = traps[a].snd - traps[b].snd;
    if(dx < 0 or dy < 0) return res = 0;
    return res = C(dx + dy, dx);
}

int dp1[30][30];
// paths from trap a to b passing through no other traps

// a > b
int numPaths(int a, int b){
    int &res = dp1[a][b];
    if(res != -1) return res;
    if(traps[a].fst - traps[b].fst < 0 or traps[a].snd - traps[b].snd < 0) return res = 0;
    res = ways(a, b);
    //cout << a << " " << b << endl;
    //cout << "sres " <<res <<endl;
    for(int t : adj[a]) if(t!=b){
        int o = mod(ways(a, t) * numPaths(t, b));
        //cout << a << " " << t << " " << b << endl;
        //cout << "o " << o << " " << ways(traps[a].fst - traps[t].fst, traps[a].snd - traps[t].snd) << " " <<  numPaths(t, b) << endl;
        res -= o;
    }
    //cout << "res " << res << endl;
    res = mod(res);
    return res;
}

int dp2[30][100];

// from trap a to 0, 0 through at least t traps
int f(int a, int t){
    //cout << a << " " << t << endl;
    int &res = dp2[a][t+30];
    if(res != -1) return res;
    if(a == 0){
        return res = (t < 0);
    }
    res = 0;
    for(int k : adj[a]){
        res = mod(res + f(k, t-1) * numPaths(a, k) ); 
    }
    return res;
}

signed main(){
    FOR(i, 0, 30) FOR(j, 0, 30) dp1[i][j] = -1;
    FOR(i, 0, 30) FOR(j, 0, 100) dp2[i][j] = -1;
    FOR(i, 0, 30) FOR(j, 0, 30) dp3[i][j] = -1;

    fast_io();
    cin >> N >> M >> K >> T >> Z;
    bitset<NMAX*4> isPrime;
    isPrime.set();
    isPrime[0] = isPrime[1] = 0;    
    
    for(int i = 0; i*i < NMAX*4; i++){
        if(isPrime[i])
        for(int j = 2*i; j < NMAX*4; j += i){
            isPrime[j] = 0;
        }
    }
    FOR(i, 0, NMAX*4) if(isPrime[i]) primes.pb(i);
    //cout << C(5, 2) << endl;

    traps.pb({0, 0});
    FOR(i, 0, K) {
        int x, y;
        cin >> x >> y;
        traps.pb({x, y});
    }
    traps.pb({N, M});
    FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
        if(i != j and traps[i].fst <= traps[j].fst and traps[i].snd <= traps[j].snd){
            adj[j].pb(i);
        }
    }

    /*
    FOR(i, 0, traps.size()) {
        FOR(j, 0, traps.size()){
            numPaths(i, j);
            //cout << << " "; 
        }
        //cout << endl;
    }


    FOR(i, 0, traps.size()) {
        FOR(j, 0, traps.size()){
            cout << numPaths(i, j) << " "; 
        }
        cout << endl;
    }
*/

    //cout << f( (int) traps.size()-1, 0) << endl;
    cout << mod(ways(K+1, 0) - f( (int) traps.size()-1, T+1) ) << endl;
}

/*

300000 300000 20 10 1000000007
18467 41
26500 6334
15724 19169
29358 11478
24464 26962
28145 5705
16827 23281
491 9961
11942 2995
5436 4827

14604 32391
153 3902
12382 292
18716 17421
19895 19718
21726 5447
11538 14771
19912 1869
26299 25667
9894 17035




*/

Compilation message (stderr)

turtle.cpp: In function 'int main()':
turtle.cpp:6:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
turtle.cpp:129:5: note: in expansion of macro 'FOR'
     FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
     ^~~
turtle.cpp:6:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
turtle.cpp:129:29: note: in expansion of macro 'FOR'
     FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
                             ^~~

• Subtask 1: 100 / 100