Submission #52085

#	Time	Username	Problem	Language	Result	Execution time	Memory
52085		FLDutchman	Energetic turtle (IZhO11_turtle)	C++14	75 / 100	2077 ms	1784 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 ways(int dx, int dy){
    if(dx < 0 or dy < 0) return 0;
    return 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(traps[a].fst - traps[b].fst, traps[a].snd - traps[b].snd);
    //cout << a << " " << b << endl;
    //cout << "sres " <<res <<endl;
    for(int t : adj[a]) if(t!=b){
        int o = mod(ways(traps[a].fst - traps[t].fst, traps[a].snd - traps[t].snd) * 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;

    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(N, M) - f( (int) traps.size()-1, T+1) ) << endl;
}

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:123: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:123:29: note: in expansion of macro 'FOR'
     FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
                             ^~~

• Subtask 1: 75 / 100