【Codeforces Round #418 (Div. 2)】Codeforces 814E An unavoidable detour for home

그림을 최단로에 따라 층을 나누면 이 그림은 모든 점이 위로 올라가고 한 변만 있고 더 위로 올라가는 변이 없다는 것을 만족시켜야 한다.우리는 dp[u][i][j][k][l]로 앞의 u개 노드를 나타낸다. 윗층에는 i개의 읽기 1이 있는 플러그와 j개의 도수가 2인 플러그가 있고 이 층에는 k개의 도수가 1인 플러그와 l개의 도수가 2인 플러그가 있다.최단로가 얼마나 되는지 신경 쓸 필요조차 없다.대대적으로 토론하고 옮기면 돼.현재 점은 먼저 윗층의 한 점과 연결되고 나머지 도수는 남을 수도 있고 이 층의 아무렇게나 연결할 수도 있다.

#include
#include
#include
using namespace std;
#define LL long long
#define DP dp[c][j][k][x][y]
const int p=1000000007;
int d[55],n;
LL dp[2][51][51][51][51];
void upd(LL &x,LL y)
{
    x+=y;
    x%=p;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&d[i]);
    dp[0][d[1]==2][d[1]==3][d[2]==2][d[2]==3]=1;
    for (int i=2,c=0;i0,sizeof(dp[c])),c^=1)
        for (int j=0;j<=i;j++)
            for (int k=0;j+k<=i;k++)
                for (int x=0;j+k+x<=i;x++)
                    for (int y=0;j+k+x+y<=i;y++)
                        if (DP)
                        {
                            if (!j&&!k)
                            {
                                if (x||y) upd(dp[c][x][y][0][0],DP);
                                continue;
                            }
                            if (d[i+1]==2)
                            {
                                if (j)
                                {
                                    upd(dp[c^1][j-1][k][x+1][y],DP*j);
                                    if (x) upd(dp[c^1][j-1][k][x-1][y],DP*j*x);
                                    if (y) upd(dp[c^1][j-1][k][x+1][y-1],DP*j*y);
                                }
                                if (k)
                                {
                                    upd(dp[c^1][j+1][k-1][x+1][y],DP*k);
                                    if (x) upd(dp[c^1][j+1][k-1][x-1][y],DP*k*x);
                                    if (y) upd(dp[c^1][j+1][k-1][x+1][y-1],DP*k*y);
                                }
                            }
                            else
                            {
                                if (j)
                                {
                                    upd(dp[c^1][j-1][k][x][y+1],DP*j);
                                    if (x) upd(dp[c^1][j-1][k][x][y],DP*j*x);
                                    if (y) upd(dp[c^1][j-1][k][x+2][y-1],DP*j*y);
                                    if (x>=2) upd(dp[c^1][j-1][k][x-2][y],DP*j*x*(x-1)/2);
                                    if (x&&y) upd(dp[c^1][j-1][k][x][y-1],DP*j*x*y);
                                    if (y>=2) upd(dp[c^1][j-1][k][x+2][y-2],DP*j*y*(y-1)/2);
                                }
                                if (k)
                                {
                                    upd(dp[c^1][j+1][k-1][x][y+1],DP*k);
                                    if (x) upd(dp[c^1][j+1][k-1][x][y],DP*k*x);
                                    if (y) upd(dp[c^1][j+1][k-1][x+2][y-1],DP*k*y);
                                    if (x>=2) upd(dp[c^1][j+1][k-1][x-2][y],DP*k*x*(x-1)/2);
                                    if (x&&y) upd(dp[c^1][j+1][k-1][x][y-1],DP*k*x*y);
                                    if (y>=2) upd(dp[c^1][j+1][k-1][x+2][y-2],DP*k*y*(y-1)/2);
                                }
                            }
                        }
    printf("%I64d
",dp[n&1][0][0][0][0]);
}