E - Coloring（组合数学/图论/dfs/dp）

题目

题意：

给定n个点 ( x i , y i ) (x_i,y_i) (xi​,yi​)，2j。如果不存在边 j − > i j->i j−>i，不妨设离j最近的点为k，此时有i,j颜色相同，而 d ( j , k ) < d ( i , j ) d(j,k)i j−>i，我们可以继续找其他的点k，使得其满足不存在边 k − > i k->i k−>i或不满足 k − > i k->i k−>i即可（因为根据情况1，我们总能找到的）。

对于第2种情况， s ( i ) s(i) s(i)可以选择相同颜色，也选择全部不同的颜色。这个根据条件1，很好理解。

有了以上两个结合，我们即可计算了。定义 d p [ i ] [ j ] dp[i][j] dp[i][j]表示取前i个点集，用j种颜色，可以组成的方案数。最终答案为 ∑ j = 1 n d p [ m ] [ j ] ∗ A ( n , j ) \sum_{j=1}^ndp[m][j]*A(n,j) ∑j=1n​dp[m][j]∗A(n,j)，其中m表示建图组成的孤立点+点集个数。

代码

#include

using namespace std;

const int N = 143;
const int K = 5;
const int MOD = 998244353;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x  0)
    {
        if(y % 2 == 1) z = mul(z, x);
        x = mul(x, x);
        y /= 2;
    }
    return z;
}

int fact[N];
int rfact[N];

int A(int n, int k)
{
    return mul(fact[n], rfact[n - k]);
}

int n;

vector g[N];
int x[N];
int y[N];
int dist[N][N];
int color[N];
int dp[N][N];

int cc = 0;
set pts;
vector compsize;

void dfs1(int i)
{
    //cerr