Submission #880304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
880304	2023-11-29T06:41:23 Z	alexdd	Energetic turtle (IZhO11_turtle)	C++17	45 / 100	287 ms	33416 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)
                {
                    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	1 ms	2392 KB	Output is correct
2	Incorrect	1 ms	6492 KB	Output isn't correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	4 ms	8540 KB	Output is correct
5	Correct	115 ms	21188 KB	Output is correct
6	Incorrect	2 ms	6492 KB	Output isn't correct
7	Correct	10 ms	8664 KB	Output is correct
8	Correct	2 ms	6492 KB	Output is correct
9	Correct	34 ms	10768 KB	Output is correct
10	Correct	72 ms	14940 KB	Output is correct
11	Correct	46 ms	12880 KB	Output is correct
12	Incorrect	164 ms	27456 KB	Output isn't correct
13	Incorrect	112 ms	14928 KB	Output isn't correct
14	Incorrect	61 ms	14932 KB	Output isn't correct
15	Incorrect	177 ms	25224 KB	Output isn't correct
16	Incorrect	242 ms	31860 KB	Output isn't correct
17	Incorrect	153 ms	21072 KB	Output isn't correct
18	Incorrect	286 ms	33360 KB	Output isn't correct
19	Incorrect	287 ms	33416 KB	Output isn't correct
20	Incorrect	226 ms	33384 KB	Output isn't correct