限制颜色数的同色不相邻染色计数

· · 题解

题目链接

要将 n=\sum_{i=1}^kc_i 个格子上色。总共 k 种颜色，第 i 种要填 c_i 格，相邻格子不能同色，求方案数。

这个题我确实没想到什么简洁快速的做法，本题解仅作为抛砖引玉。
在末尾补充了优化做法，就是比原做法更简单还快的。

设 k 元生成函数 F_k(x_1,\cdots ,x_k)，其对应 x_1^{c_1}\cdots x_k^{c_k} 系数表示答案。那么可以得到递推

F_k=F_{k-1}+\frac{(1+F_{k-1})^2x_k}{1-F_{k-1}x_k}

现在尝试提取其 [x_k^{c_k}] 系数，就得到一个关于 F_{k-1} 的多项式，如此就从 k 元的情况变为 k-1 元了。要进一步推下去，就要考虑将 [x^m_{k}]F_k^n 表示为关于 F_{k-1} 的多项式：

\begin{aligned}[x^m_k]F_k^n&=[x_k^m]\left(F_{k-1}+\frac{(1+F_{k-1})^2x_k}{1-F_{k-1}x_k} \right)^n \\&=[x^m_k]\sum_{i=0}^{\min(n,m)}\binom ni \left( \frac{(1+F_{k-1})^2x_k}{1-F_{k-1}x_k}\right)^iF_{k-1}^{n-i} \\&=[x_k^m]\sum_{i=0}^{\min(n,m)}\binom ni(1+F_{k-1})^{2i}F_{k-1}^{n-i}x_k^i\sum_{j=0}^{m-i}\binom{j+i-1}{j}F_{k-1}^jx_k^j \\ &=\sum_{i=0}^{\min(n,m)}\binom ni (1+F_{k-1})^{2i}F_{k-1}^{n-i}\binom{m-1}{m-i}F_{k-1}^{m-i}\end{aligned}

可以发现一个关于 F_k 的 n 次多项式经过此变换后就得到了 F_{k-1} 的 n+m 次多项式。整理一下的话，就是给定一个 n 次多项式 f(x) 和参数 m（m\leq n），求出：

g(x)=\sum_{j=0}^n f_j\sum_{i=1}^{\min(m,j)}\binom ji \binom{m-1}{m-i}(1+x)^{2i}x^{j+m-2i}

一次变换的复杂度可以做到 \Theta(nm)（因为内层和式的系数可以整式递推），这样做总时间复杂度就是 \mathcal O(m^2k^2)，其中 m=\max\{c_i \}。不过这题中 m 太小，暴力计算 g(x) 也是可以通过的。

最后的问题就是，这个做法如何继续优化呢？感觉有点困难，还请指点一下。

参考代码：

// this is just a trivial and brutal solution.

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define N 262147
#define ll long long
#define p 1000000007
using namespace std;

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

int fac[N],ifac[N];

void init(int n){
    fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for(int i=2;i<=n;++i) fac[i] = (ll)fac[i-1]*i%p;
    ifac[n] = power(fac[n],p-2);
    for(int i=n-1;i;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
}

inline int binom(int n,int m){
    if(n<m) return 0;
    return (ll)fac[n]*ifac[m]%p*ifac[n-m]%p;
}

void transform(const int *f,int n,int m,int *r){
    static int g[N];
    memset(g,0,(n+m+1)<<2);
    for(int k=0;k<=n;++k)
    for(int i=1;i<=min(m,k);++i){
        int tmp = (ll)f[k]*binom(k,i)%p*binom(m-1,m-i)%p,t;
        for(int j=0;j<=(i<<1);++j){
            t = k+m-(i<<1)+j;
            g[t] = (g[t]+(ll)tmp*binom(i<<1,j))%p;
        }
    }
    memcpy(r,g,(n+m+1)<<2);
}

int f[N];
int T,k,m,deg;

int main(){
    init(23333);
    scanf("%d",&T);
    while(T--){
        scanf("%d",&k);
        f[1] = deg = 1;
        for(int i=1;i<k;++i){
            scanf("%d",&m);
            transform(f,deg,m,f);
            deg += m;
        }
        scanf("%d",&m);
        printf("%d\n",f[m]);
        memset(f,0,(deg+1)<<2);
    }
    return 0;   
}

实际上这题用容斥就很简单。枚举对于每种颜色，产生的相邻对数 p_1,\cdots,p_k（0\le p_i < c_i），然后计算此条件下的排列数（就是至少有 p_1+\cdots+p_k 对相邻的排列数）。答案就应该是

\sum_{p_1,\cdots,p_k}(-1)^{\sum_{j=1}^kp_j} \left(\frac{(\sum_{j=1}^k(c_j-p_j))!}{\prod_{j=1}^k(c_j-p_j)!}\right)\prod_{j=1}^kF(c_j,p_j)

这个式子中 (-1) 的幂表示容斥系数；
括号里面那一大块是个多重排列，因为强制 p_j 对同色块相邻，而每一对绑定在一起都会让自由排列的元素数量减 1；
最后那个 F 表示将 c_j 拆分为 c_j-p_j 个部分的方案数，可以知道它等于 \dbinom{c_j-1}{p_j}。

这个式子就可以用生成函数改写一下了，设

G(m;x)=\sum_{i=1}^m\binom{m-1}{m-i} \frac{(-1)^{m-i} x^i}{i!}

则答案为

\sum_{t\geq 1}t! [x^t]\prod_{i=1}^kG(c_i;x)

设 n=c_1+\cdots+c_k，使用分治乘即可做到 \Theta(n \log^2 n) 的时间复杂度。（如果暴力乘的话，和上面说到的做法复杂度相同）