답안 #524241

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524241 2022-02-08T20:54:55 Z TheKingAleks 힘 센 거북 (IZhO11_turtle) C++14
100 / 100
174 ms 50628 KB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX_K = 25;
const ll MAX_N = 6e6+2;
ll MOD=1e9+7;
ll dp1[MAX_K][MAX_K]; /// i1 -> i2 kato stupvash na i2 i produljavash
ll dp2[MAX_K][MAX_K]; /// i1 -> i2, kato sled i2 nqma drugi kapani
ll dist[MAX_K][MAX_K];
ll n,m,k,t;
ll primes[MAX_N],primes_br = 0,vis[MAX_N];
pair<ll,ll> traps[MAX_K];
void sieve()
{
    for(ll i=2; i<=MAX_N; i++)
    {
        if(vis[i]) continue;
        primes[primes_br] = i; primes_br++;
        for(ll j=2*i; j<=MAX_N; j+=i) vis[j] = true;
    }
}
ll find_power(ll num, ll p)
{
    ll res = 0;
    while(num > 0)
    {
        num/=p;
        res+=num;
    }
    return res;
}
ll fast_pow(ll num, ll st)
{
    if(st == 0) return 1LL;
    ll temp = fast_pow(num,st/2LL);
    if(st&1) return ((((temp*temp)%MOD)*num)%MOD);
    return ((temp*temp)%MOD);
}
ll combi(ll k, ll n)
{
    ll res = 1LL;
    for(ll i=0; primes[i]<=n; i++)
    {
        ll pw = find_power(n,primes[i])-find_power(k,primes[i])-find_power(n-k,primes[i]);
        res *= fast_pow(primes[i],pw);
        res %= MOD;
    }
    return res;
}
ll no_traps(ll start_idx, ll end_idx)
{
    if(dp2[start_idx][end_idx]) return dp2[start_idx][end_idx];
    ll res = dist[start_idx][end_idx];
    for(ll middle_idx=start_idx+1; middle_idx<=end_idx-1; middle_idx++)
    {
        if(traps[start_idx].second <= traps[middle_idx].second && traps[middle_idx].second <= traps[end_idx].second)
        {
            res -= (no_traps(start_idx,middle_idx)*dist[middle_idx][end_idx])%MOD;
            while(res < 0LL) res += MOD;
            res %= MOD;
        }
    }
    dp2[start_idx][end_idx] = res;
    return res;
}
ll rec(ll idx, ll stepped_traps)
{
    if(idx == k+1) return 1LL;
    if(stepped_traps > t) return 0LL;
    if(dp1[idx][stepped_traps]) return dp1[idx][stepped_traps];
    ll res = 0;
    for(ll next_idx = idx+1; next_idx <= k+1; next_idx++)
    {
        if(traps[idx].second <= traps[next_idx].second)
        {
            res += (no_traps(idx,next_idx)*rec(next_idx,stepped_traps+1LL))%MOD;
            res %= MOD;
        }
    }
    dp1[idx][stepped_traps] = res;
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    sieve();
    cin>>n>>m>>k>>t>>MOD;
    traps[0] = {0,0};
    ll x1,y1;
    for(ll i=1; i<=k; i++)
    {
        cin>>x1>>y1;
        traps[i] = {x1,y1};
    }
    traps[k+1] = {n,m};
    sort(traps,traps+k+1);
    for(ll i=0; i<=k+1; i++)
    {
        for(ll j=i+1; j<=k+1; j++)
        {
            if(traps[i].second <= traps[j].second)
            {
                dist[i][j] = combi(traps[j].first-traps[i].first,traps[j].first-traps[i].first+traps[j].second-traps[i].second);
            }
        }
    }
    cout<<rec(0,0)<<endl;
}
/**
4 4 2 1 1000000007
1 1
2 2
*/

Compilation message

turtle.cpp: In function 'void sieve()':
turtle.cpp:17:17: warning: iteration 6000000 invokes undefined behavior [-Waggressive-loop-optimizations]
   17 |         if(vis[i]) continue;
      |            ~~~~~^
turtle.cpp:15:18: note: within this loop
   15 |     for(ll i=2; i<=MAX_N; i++)
      |                 ~^~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 50464 KB Output is correct
2 Correct 133 ms 50512 KB Output is correct
3 Correct 113 ms 50464 KB Output is correct
4 Correct 111 ms 50464 KB Output is correct
5 Correct 128 ms 50480 KB Output is correct
6 Correct 119 ms 50464 KB Output is correct
7 Correct 116 ms 50500 KB Output is correct
8 Correct 117 ms 50444 KB Output is correct
9 Correct 124 ms 50464 KB Output is correct
10 Correct 121 ms 50500 KB Output is correct
11 Correct 139 ms 50476 KB Output is correct
12 Correct 162 ms 50492 KB Output is correct
13 Correct 133 ms 50468 KB Output is correct
14 Correct 141 ms 50628 KB Output is correct
15 Correct 144 ms 50520 KB Output is correct
16 Correct 159 ms 50460 KB Output is correct
17 Correct 154 ms 50504 KB Output is correct
18 Correct 174 ms 50460 KB Output is correct
19 Correct 172 ms 50476 KB Output is correct
20 Correct 172 ms 50460 KB Output is correct