Submission #52085

#TimeUsernameProblemLanguageResultExecution timeMemory
52085FLDutchmanEnergetic turtle (IZhO11_turtle)C++14
75 / 100
2077 ms1784 KiB
#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()){
                             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...