oj.uz

답안 #880105

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
880105 2023-11-28T17:58:20 Z alexdd 힘 센 거북 (IZhO11_turtle) C++17
5 / 100
 2000 ms 25204 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 inde;
int comb(int x, int y)
{
    return (((((fact[x]*put(fact[y],inde-1)%MOD)*put(fact[x-y],inde-1))%MOD)));
}
int calc_inde(int x)
{
    int d=2;
    int prod = n, 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;
    for(int i=1;i<=n+m;i++)
        fact[i] = (fact[i-1]*i)%MOD;
    for(int i=0;i<k;i++)
    {
        cin>>traps[i].first>>traps[i].second;
    }
    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%=MOD;
                }
                break;
            }
        }
    }
    cout<<rez;
    return 0;
}
/**
1 4 2 1 100000
0 3
1 3
*/

Subtask #1
5.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Incorrect 57 ms 4716 KB Output isn't correct
5 Incorrect 219 ms 18772 KB Output isn't correct
6 Incorrect 3 ms 6488 KB Output isn't correct
7 Incorrect 83 ms 8540 KB Output isn't correct
8 Incorrect 1 ms 6488 KB Output isn't correct
9 Execution timed out 2088 ms 8456 KB Time limit exceeded
10 Execution timed out 2058 ms 8532 KB Time limit exceeded
11 Incorrect 96 ms 10836 KB Output isn't correct
12 Execution timed out 2065 ms 17088 KB Time limit exceeded
13 Incorrect 6 ms 10844 KB Output isn't correct
14 Incorrect 610 ms 10832 KB Output isn't correct
15 Incorrect 335 ms 21068 KB Output isn't correct
16 Execution timed out 2033 ms 14440 KB Time limit exceeded
17 Execution timed out 2059 ms 14936 KB Time limit exceeded
18 Execution timed out 2076 ms 14972 KB Time limit exceeded
19 Execution timed out 2031 ms 15188 KB Time limit exceeded
20 Incorrect 473 ms 25204 KB Output isn't correct