oj.uz

답안 #765582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
765582 2023-06-24T21:16:10 Z Deepesson 캥거루 (CEOI16_kangaroo) C++17
0 / 100
 1 ms 312 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Incorrect 1 ms 308 KB Output isn't correct
3 Halted 0 ms 0 KB -