Submission #1199407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199407		noyancanturk	Energetic turtle (IZhO11_turtle)	C++20	10 / 100	33 ms	9412 KiB

turtle

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int> 
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " << 
#define all(x) x.begin(),x.end()
using namespace std;
int phi = 1;
int n,m,k,t,z;
int Z;

int add(int x,int y) {
    if (x+y >= Z) return x+y-Z;
    return x+y;
}

int mult(int x,int y) {
    return (x*y)%Z;
}

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;
}

int r(int x,int y) {
    if (x < y) return 0;
    return x/y+r(x/y,y);
}

const int N = 1e6+1;

vi primes;
vi sieve(N,0);
int nck(int n,int k) {
    if (n < k || k < 0 || n < 0) return 0;
    int ans = 1;
    for (auto it : primes) {
        int a = r(n,it);
        if (!a) break;
        int b = r(k,it),c = r(n-k,it);
        ans = mult(ans,expo(it,a-b-c));
    }    
    return ans;
}

void solve() {
    cin >> n >> m >> k >> t >> z;
    Z = z;
    for (int i=2;i<N;i++) {
        if (!sieve[i]) {
            sieve[i] = i;
            primes.push_back(i);
            for (int j = i*i;j<N;j+=i) sieve[j] = i;
        }
    }
    vector<pii> traps(k+2);
    traps[0] = {0,0},traps[1] = {n,m};
    for (int i = 2;i<k+2;i++) cin >> traps[i].ff >> traps[i].ss;
    sort(all(traps));
    int ways[k+2][k+2];
    for (int i = 0;i<k+2;i++) {
        ways[i][i] = 1;
        for (int j = i-1;j>=0;j--) {
            ways[j][i] = nck(traps[i].ff-traps[j].ff+traps[i].ss-traps[j].ss,traps[i].ff-traps[j].ff);
            for (int jj = j+1;jj<i;jj++) {
                ways[j][i] = add(ways[j][i],Z-mult(ways[j][jj],ways[jj][i]));
            }
        }
    }
    int dp[k+2][t+2]{};
    dp[0][0] = 1;
    for (int j = 1;j<=t+1;j++) {
        for (int i=1;i<k+2;i++) {
            dp[i][j] = 0;
            for (int jj = 0;jj<i;jj++) {
                dp[i][j] = add(dp[i][j],mult(dp[jj][j-1],ways[jj][i]));
            }
        }
    }
    int ans = 0;
    for (int i = 1;i<=t+1;i++) ans = add(ans,dp[k+1][i]);
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

• Subtask 1: 10 / 100