Submission #765582

#	Time	Username	Problem	Language	Result	Execution time	Memory
765582		Deepesson	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	1 ms	312 KiB

kangaroo

#include <bits/stdc++.h>
#define MAX 205
using ll = long long;
///Como funciona isso aqui?
///Todo cara OU eh aberto E fechado pela direita, ou eh aberto E fechado pela esquerda. Soh tem essas duas opcoes.

int N;
ll bits[MAX];
ll tab[MAX][MAX][MAX];
bool existe[MAX][MAX][MAX];
ll MOD = 2LL*(1e9+7);
ll dp(ll pos,ll v1,ll v2){
    if(pos==N){
        if(!v1&&!v2)return 1;
        return 0;
    }
    if(existe[pos][v1][v2])return tab[pos][v1][v2];
    existe[pos][v1][v2]=1;
    ll res=0;
    if(bits[pos]==1){///Caso especial
        res=dp(pos+1,v1,v2+1);///Caso 1: Conecta com a direita
        ///Caso 2: Conecta na esquerda com um v1
        if(v1)res=(res+(v1*dp(pos+1,v1-1,v2+1)))%MOD;
        ///Caso 3: Conecta na esquerda com um v2
        if(v2)res=(res+(v2*dp(pos+1,v1,v2-1)))%MOD;
    }else {
        ///Caso 1: Conecta na direita
        res=dp(pos+1,v1+1,v2);
        ///CONECTANDO NA ESQUERDA
        ///Caso 2: Conecta dois v1s
        if(v1>1){
            ll base = v1*(v1-1)*dp(pos+1,v1-2,v2+2)%MOD;
            res=(res+base)%MOD;
        }
        ///Caso 3: Conecta dois v2s
        if(v2>1){
            ll base = v2*(v2-1)*dp(pos+1,v1,v2-2)%MOD;
            res=(res+base)%MOD;
        }
        ///Caso 4: Conecta um v1 e um v2
        if(v1&&v2){
            ll base = v1*(v2)*dp(pos+1,v1-1,v2)%MOD;
            res=(res+base)%MOD;
        }
    }
    return tab[pos][v1][v2]=res;
}
int main()
{
    for(auto&x:bits)x=2;
    std::cin>>N;
    for(int i=0;i!=2;++i){
        int a;
        std::cin>>a;
        --a;
        bits[a]--;
    }
    std::cout<<dp(0,0,0)/2LL<<"\n";
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 30
• Subtask 3: 0 / 15
• Subtask 4: 0 / 49