Submission #58379

#	Time	Username	Problem	Language	Result	Execution time	Memory
58379		Benq	Energetic turtle (IZhO11_turtle)	C++14	100 / 100	970 ms	75640 KiB

turtle

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

namespace NT {
    vpi fac(int x) {
        vpi pri;
        
        for (int i = 2; i*i <= x; ++i) if (x % i == 0) {
            int t = 0;
            while (x % i == 0) x /= i, t ++;
            pri.pb({i,t});
        }
        
        if (x > 1) pri.pb({x,1});
        return pri;
    }

    int phi(int x) {
        for (auto a: fac(x)) x /= a.f, x *= a.f-1; 
        return x;
    }

    ll inv(ll a, ll b) { // 0 < a < b, gcd(a,b) = 1
        a %= b;
        if (a <= 1) return a;
        ll i = inv(b%a,a);
        ll tmp = -((b/a)*i+((b%a)*i)/a) % b;
        if (tmp < 0) tmp += b;
        return tmp;
    }
 
    pl CRT(pl a, pl b) { // Chinese Remainder Theorem, Verified by Kattis generalchineseremainder
        ll g = __gcd(a.s,b.s), l = a.s*b.s/g;
        if ((b.f-a.f) % g != 0) return {-1,-1};
        ll A = a.s/g, B = b.s/g;
        ll mul = (b.f-a.f)/g*inv(A%B,B) % B;
        return {((mul*a.s+a.f)%l+l)%l,l};
    }
};

template<int SZ> struct ComboPower {
    pl fac[SZ+1], ifac[SZ+1], mod;
    ll MOD = 1;
    
    void init(pl _mod) { // prime, power
        mod = _mod; F0R(i,mod.s) MOD *= mod.f;
        
        fac[0] = ifac[0] = {1,0};
        FOR(i,1,SZ+1) {
            fac[i] = fac[i-1];
            int I = i, z = 0;
            while (I % mod.f == 0) I /= mod.f, z++;
            fac[i].f = fac[i].f*I%MOD; fac[i].s += z;
            ifac[i] = {NT::inv(fac[i].f,MOD),fac[i].s};
        }
    }

    ll comb(ll a, ll b) {
        if (a < b || b < 0) return 0;
        ll tmp = (fac[a].f*ifac[b].f%MOD)*ifac[a-b].f % MOD;
        ll z = fac[a].s-fac[b].s-fac[a-b].s;
        if (z >= mod.s) return 0;
        F0R(i,z) tmp = tmp*mod.f % MOD;
        return tmp;
    }
};

template<int SZ> struct ComboGeneral {
    vector<ComboPower<SZ>> v;
    ll MOD;
    
    void init(ll _MOD) {
        MOD = _MOD;
        for (auto a: NT::fac(MOD)) {
            v.pb(ComboPower<SZ>());
            v.back().init(a);
        }
    }
    
    ll comb(ll a, ll b) {
        pl cur = {0,1};
        for (auto& x: v) cur = NT::CRT({x.comb(a,b),x.MOD},cur);
        return cur.f;
    }
};


ComboGeneral<600001> C;

int get(pi a, pi b) {
    return C.comb(b.f-a.f+b.s-a.s,b.s-a.s);
}

int N,M,K,T,Z, ways[22][22], dp[22][22];
vpi p;

ll ad(ll a, ll b) { return (a+b)%Z; }
ll sub(ll a, ll b) { return (a-b+Z)%Z; }
ll mul(ll a, ll b) { return a*b%Z; }

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> K >> T >> Z;
    C.init(Z);
    F0R(i,K) {
        int X,Y; cin >> X >> Y;
        p.pb({X,Y});
    }
    p.pb({0,0});
    sort(all(p));
    p.pb({N,M});
    F0R(i,sz(p)) F0Rd(j,i) {
        ways[j][i] = get(p[j],p[i]);
        FOR(k,j+1,i) ways[j][i] = sub(ways[j][i],mul(ways[j][k],get(p[k],p[i])));
        // cout << j << " " << i << " " << ways[j][i] << "\n";
    }
    dp[0][0] = 1;
    FOR(i,1,sz(p)) F0R(j,i) FOR(k,1,T+2) 
        dp[i][k] = ad(dp[i][k],mul(dp[j][k-1],ways[j][i]));
    
    int ans = 0;
    FOR(i,1,T+2) ans = ad(ans,dp[sz(p)-1][i]);
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 100 / 100