Submission #880304

#	Time	Username	Problem	Language	Result	Execution time	Memory
880304		alexdd	Energetic turtle (IZhO11_turtle)	C++17	45 / 100	287 ms	33416 KiB

turtle

#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 comb(int x, int 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;
    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 / 100