oj.uz

Submission #880333

# Submission time Handle Problem Language Result Execution time Memory
880333 2023-11-29T07:50:21 Z alexdd Energetic turtle (IZhO11_turtle) C++17
45 / 100
 298 ms 60244 KB 
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
int n,m,k,t,MOD;
int put(int a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put((a*a)%MOD,exp/2);
    else
        return (put((a*a)%MOD,exp/2)*a)%MOD;
}
pair<int,int> traps[25];
int dp[1100000];
int ult[1100000];
int fact[6000015];
int invf[6000015];
int catet[30];
int inde;
int cmb[2005][2005];
int comb(int x, int y)
{
    if(x<=2000 && y<=2000)
        return cmb[x][y];
    return (((((fact[x]*invf[y]%MOD)*invf[x-y])%MOD)));
}
int calc_inde(int x)
{
    int d=2;
    int prod = x, imp = 1;
    while(d*d<=x)
    {
        if(x%d==0)
        {
            while(x%d==0)
                x/=d;
            prod *= d-1;
            imp *= d;
        }
        if(d==2)
            d--;
        d+=2;
    }
    if(x>1)
    {
        prod *= x-1;
        imp *= x;
    }
    return prod/imp;
}
signed main()
{
    cin>>n>>m>>k>>t>>MOD;
    for(int i=0;i<=2000;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(i==0 || j==0 || i==j)
            {
                cmb[i][j]=1;
                continue;
            }
            cmb[i][j] = (cmb[i-1][j] + cmb[i-1][j-1])%MOD;
        }
    }
    inde = calc_inde(MOD);
    fact[0]=1;
    invf[0]=1;
    for(int i=1;i<=n+m;i++)
    {
        fact[i] = (fact[i-1]*i)%MOD;
        invf[i] = put(fact[i], inde-1);
    }
    for(int i=0;i<k;i++)
    {
        cin>>traps[i].first>>traps[i].second;
    }
    for(int i=1;i<=k;i++)
    {
        catet[i]=0;
        for(int config=0;config<(1<<i)-1;config++)
        {
            int cnt2=0;
            for(int j=0;j<i;j++)
            {
                if((((1<<j)&config)))
                    cnt2++;
            }
            if(cnt2>t)
                catet[i]++;
        }
    }
    sort(traps,traps+k);
    int rez=comb(n+m,n);
    for(int config=1;config<(1<<k);config++)
    {
        int cnt=0;
        for(int i=0;i<k;i++)
            if(((1<<i)&config))
                cnt++;
        for(int i=0;i<k;i++)
        {
            if(((1<<i)&config) && (cnt==1 || (traps[ult[config-(1<<i)]].first <= traps[i].first && traps[ult[config-(1<<i)]].second <= traps[i].second)))
            {
                ult[config]=i;
                if(cnt>1)
                {
                    int j = ult[config-(1<<i)];
                    dp[config] = (dp[config-(1<<i)] * comb((traps[i].first - traps[j].first) + (traps[i].second - traps[j].second), (traps[i].second - traps[j].second)))%MOD;
                }
                else
                    dp[config] = comb(traps[i].first + traps[i].second, traps[i].first);
                //cout<<config<<"  "<<dp[config]<<" "<<comb(n - traps[i].first + m - traps[i].second, n - traps[i].first)<<" zzz\n";
                if(cnt>t)
                {
                    if((cnt-t)%2==1)
                        rez = rez + MOD - (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD;
                    else
                        rez = rez + (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD;
                    rez%=MOD;
                    /*for(int config2=0;config2<(1<<cnt)-1;config2++)
                    {
                        int cnt2=0;
                        for(int u=0;u<cnt;u++)
                            if((((1<<u)&config2)))
                                cnt2++;
                        if(cnt2>t)
                            rez = (rez + (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD)%MOD;
                    }*/
                    //rez = rez + (catet[cnt] * ((dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD))%MOD;
                    //rez%=MOD;
                }
                break;
            }
        }
    }
    cout<<rez;
    return 0;
}
/**
1 4 2 1 100000
0 3
1 3

1 1 1 0 1000
0 1

*/

Subtask #1
45.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 35156 KB Output is correct
2 Incorrect 13 ms 39260 KB Output isn't correct
3 Correct 13 ms 39260 KB Output is correct
4 Correct 15 ms 39456 KB Output is correct
5 Correct 117 ms 52504 KB Output is correct
6 Incorrect 14 ms 39260 KB Output isn't correct
7 Correct 19 ms 39260 KB Output is correct
8 Correct 13 ms 39260 KB Output is correct
9 Correct 45 ms 43348 KB Output is correct
10 Correct 69 ms 47444 KB Output is correct
11 Correct 57 ms 41300 KB Output is correct
12 Incorrect 173 ms 55632 KB Output isn't correct
13 Incorrect 123 ms 47444 KB Output isn't correct
14 Incorrect 71 ms 41304 KB Output isn't correct
15 Incorrect 191 ms 54100 KB Output isn't correct
16 Incorrect 253 ms 60244 KB Output isn't correct
17 Incorrect 164 ms 51540 KB Output isn't correct
18 Incorrect 298 ms 60184 KB Output isn't correct
19 Incorrect 296 ms 60184 KB Output isn't correct
20 Incorrect 237 ms 60240 KB Output isn't correct