题解：P16149 [ICPC 2017 NAIPC] Maximum Color Clique

· · 题解

题意简述

给定一个边染色的完全图，保证每个简单环上都存在两条颜色相同的相邻边。对每个非空点集，求其中最大单色团的大小，再将所有结果相加，对 10^9+7 取模。

解题思路

先证明：满足条件的完全图一定存在一个节点，它向所有其他节点连出的边颜色相同。不断删除这样的节点，就能把原图化为一个有序的颜色序列。

对节点数归纳。节点数不超过 2 时结论成立。任取节点 v，根据归纳假设，删去 v 后存在节点 x，它向其他节点的边均为颜色 a。

若边 vx 也是颜色 a，则 x 就是所求节点。否则记边 vx 的颜色为 b，其中 a\ne b。对于其他节点 z，三角形 v,x,z 不能三条边颜色各不相同，所以边 vz 的颜色只能为 a 或 b。

若 v 连出的边均为 b，则 v 满足要求。否则可以找到节点 y，使边 vy 的颜色为 a。下面证明 y 连出的所有边都是颜色 a。

边 yv 和 yx 已满足条件。任取其他节点 z，假设边 yz 的颜色为 h\ne a：

两种情况都违反题目条件，所以不存在这样的 z，归纳完成。

删除节点后，剩余图仍满足原条件。因此，依次找到并删除上述节点，得到顺序 v_1,v_2,\dots,v_n。对于 i<n，记 a_i 为 v_i 到所有后续节点的公共颜色。于是任意 i<j 的边 v_iv_j 都是颜色 a_i。最后一个节点不需要指定颜色。

现在固定一个非空点集 S，设其中最后的节点为 v_r。按颜色统计 S 在位置 1\sim r-1 中选取的节点数，记为 t_c。则有：

f(S)=1+\max_c t_c

对于下界，取出现最多的颜色 c，选出之前所有颜色为 c 的节点，再加入 v_r。每条边的颜色由较早节点决定，故这些节点构成大小为 t_c+1 的单色团。

对于上界，任意一个颜色为 c 的单色团中，除最后一个节点外，其他节点的颜色必须都是 c。这些节点都出现在 r 之前，所以团大小不超过 t_c+1。这个论证也允许团本身不包含 v_r。若 S 仅有一个节点，所有 t_c=0，公式仍给出 1。

然后按 S 的最后位置 r 分类计数。前 r-1 个位置可以任意选取。设这段前缀中颜色 c 一共出现 b_c 次，令 L=\max_c b_c。预处理二项式系数的前缀和：

B_{b,k}=\sum_{j=0}^{\min(b,k)}\binom{b}{j}

若要求所选节点中每种颜色都少于 k 个，颜色 c 对应的选择数为 B_{b_c,k-1}。各颜色的节点集合互不相交，可以独立选择，所以满足该要求的前缀子集共有：

\prod_c B_{b_c,k-1}

对任意非负整数 t，可以用「t\ge k」的成立次数求出 t。将这个计数用于 \max_c t_c，位置 r 对答案的贡献为：

\begin{aligned} A_r & =2^{r-1}+\sum_{k=1}^L\left(2^{r-1}-\prod_c B_{b_c,k-1}\right) \\ & =(L+1)2^{r-1}-\sum_{k=1}^L\prod_c B_{b_c,k-1} \end{aligned}

第一项中的 1 来自固定选取的最后节点 v_r。其余每一项统计最大颜色数量至少为 k 的前缀子集，因而不会把最大值误算成所有颜色数量之和。

代码中，第一部分扫描当前剩余节点，找到单色邻接的节点后记录其颜色到 col。二维数组 f 先计算二项式系数，再按行求前缀和，保存上述 B。cnt 维护各颜色在已处理前缀中的数量，mx 对应 L，数组 a 仅记录已经出现的颜色，未出现的颜色因子为 1，可以省略。

处理位置 r 时先计算贡献，再加入 col[r]，保证统计范围恰好是前 r-1 个位置。最后一个位置不再加入颜色。使用 B_{r-1,r-1}=2^{r-1}，也不需要另行预处理幂。

寻找删除顺序需要 O(n^3) 时间，二项式系数及其前缀和需要 O(n^2) 时间。每个前缀枚举至多 n 个阈值和至多 n 种已出现颜色，计数部分也是 O(n^3)。总空间复杂度为 O(n^2)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=305;
const int mod=1000000007;
int c[N][N],f[N][N],col[N],cnt[N],a[N];
bool vis[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)cin>>c[i][j];
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(vis[j])continue;
            int val=0;
            bool ok=1;
            for(int k=1;k<=n;k++)
            {
                if(vis[k]||j==k)continue;
                if(!val)val=c[j][k];
                else if(val!=c[j][k]){ok=0;break;}
            }
            if(ok){col[i]=val;vis[j]=1;break;}
        }
    }
    for(int i=0;i<=n;i++)
    {
        f[i][0]=f[i][i]=1;
        for(int j=1;j<i;j++)f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;
    }
    for(int i=0;i<=n;i++)
    {
        for(int j=1;j<=i;j++)f[i][j]=(f[i][j]+f[i][j-1])%mod;
    }
    int ans=0,m=0,mx=0;
    for(int i=1;i<=n;i++)
    {
        int res=(ll)(mx+1)*f[i-1][i-1]%mod;
        for(int j=1;j<=mx;j++)
        {
            int sum=1;
            for(int k=0;k<m;k++)sum=(ll)sum*f[cnt[a[k]]][min(j-1,cnt[a[k]])]%mod;
            res=(res-sum+mod)%mod;
        }
        ans=(ans+res)%mod;
        if(i<n)
        {
            if(!cnt[col[i]])a[m++]=col[i];
            cnt[col[i]]++;
            mx=max(mx,cnt[col[i]]);
        }
    }
    cout<<ans<<'\n';
    return 0;
}