Submission #880113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880113	2023-11-28T18:05:16 Z	alexdd	Energetic turtle (IZhO11_turtle)	C++17	45 / 100	297 ms	33396 KB

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)
                {
                    rez = rez + MOD - (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
*/

Subtask #1

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Incorrect	1 ms	6492 KB	Output isn't correct
3	Correct	1 ms	6492 KB	Output is correct
4	Correct	4 ms	8540 KB	Output is correct
5	Correct	113 ms	21076 KB	Output is correct
6	Incorrect	1 ms	6492 KB	Output isn't correct
7	Correct	7 ms	8540 KB	Output is correct
8	Correct	2 ms	6492 KB	Output is correct
9	Correct	35 ms	10764 KB	Output is correct
10	Correct	59 ms	14940 KB	Output is correct
11	Correct	46 ms	12896 KB	Output is correct
12	Incorrect	162 ms	27228 KB	Output isn't correct
13	Incorrect	111 ms	15444 KB	Output isn't correct
14	Incorrect	60 ms	14960 KB	Output isn't correct
15	Incorrect	200 ms	25168 KB	Output isn't correct
16	Incorrect	225 ms	31312 KB	Output isn't correct
17	Incorrect	155 ms	21076 KB	Output isn't correct
18	Incorrect	297 ms	33364 KB	Output isn't correct
19	Incorrect	291 ms	33396 KB	Output isn't correct
20	Incorrect	225 ms	33384 KB	Output isn't correct