[dp] Jzoj P5870 地图

Description

Input

Output

Sample Input

4
2 1 1 2

Sample Output

2

Data Constraint

 

 

题解

• 设f[i][j]为剩下i个1，j个2的地图数量
• 如果2号用了一条边就是1号点了
• 根据情况dp

代码

#include <cstdio>
using namespace std;
int n,num[3],f[2010][2010],mo=998244353;
int main()
{
    freopen("map.in","r",stdin);freopen("map.out","w",stdout);
    scanf("%d",&n);
    for (int x,i=1;i<=n;i++) scanf("%d",&x),num[x]++;
    f[0][0]=1;
    for (int i=0;i<=n;i++)
        for (int x=i;x>=0;x--)
        {    
            int y=i-x;
            if (x>=1&&y==0) (f[x+1][y]+=1ll*f[x-1][y]*x%mo)%=mo;
            if (x>=2) (f[x][y+1]+=1ll*f[x-2][y]*((1ll*x*(x-1)/2)%mo)%mo)%=mo;
            if (y>=2) (f[x][y+1]+=1ll*f[x+2][y-2]*((1ll*y*(y-1)/2)%mo)%mo)%=mo;
            if (i*x) (f[x][y+1]+=1ll*f[x][y-1]*x%mo*y%mo)%=mo;
        }
    printf("%d",f[num[1]][num[2]]);
}