답안 #880113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880113 2023-11-28T18:05:16 Z alexdd 힘 센 거북 (IZhO11_turtle) C++17
45 / 100
297 ms 33396 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 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
*/
# 결과 실행 시간 메모리 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