이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |