多重集的交错排列

交错排列是多重集的一种全排列。多重集的相邻元相异的全排列称为交错排列。

多重集的交错排列数的计算

对于多重集$M=\{n_i\times a_i|1\le i\le m,\sum n_i = n\}$。

我们与考虑每种元素内部的约束。 其内部约束可看作第$i$个元素和第$i+1$个元素不相邻。 考虑容斥。

$$ \sum_{b_1…b_m,b_i\in[0,n_i-1]}\frac{(\sum n_i-b_i)!}{\prod(n_i-b_i)!}\prod_{i=1}^m(-1)^{b_i}\binom{n_i-1}{b_i} $$

打破$k$个约束看作“合并$k$个集合”的过程，即用捆绑法每次将两个元素合并成一个元素，那么合并之后看成多重集全排列即可。

$O(n^2)$计算方法

考虑枚举$c_i=n_i-b_i$

$$ \sum_{c_1…c_m,c_i\in[1,n_i]}\frac{(\sum c_i)!}{\prod(c_i)!}\prod_{i=1}^m(-1)^{n_i-c_i}\binom{n_i-1}{n_i-c_i} $$

令$s=\sum c_i$

$$ \sum_{c_1…c_m,c_i\in[1,n_i]}(-1)^{n-s}\frac{s!}{\prod(c_i)!}\prod_{i=1}^m\binom{n_i-1}{n_i-c_i} $$

考虑计算后面$\frac{1}{\prod(c_i)!}\prod_{i=1}^m\binom{n_i-1}{n_i-c_i} $的值。

令$f[i][j]$为只考虑前$i$个集合且$\sum c_k = j$的值。

$$ f[i][j]=\sum_{1\le k\le \min(n_i,j)} f[i-1][j-k]\times \frac{1}{k!}\times\binom{n_i-1}{n_i-k} $$

复杂度为$\sum_{i=1}^m n_i\sum_{j=1}^{i}n_i=O(n^2)$

带标号情况的计算

P4448 [AHOI2018初中组]球球的排列

给定一个序列 $a(a_i\le 10^9)$，长度为 $n(n\le 300)$。

试求有多少 $1$ 到 $n$ 的排列 $p_i$，满足对于任意的 $2\le i\le n,2≤i≤n $有 $a_{p_i-1}\times a_{p_i+1}$ 不为完全平方数。

其“完全平方”的关系显然具有传递性，因此可以转化成上面问题带标号的情况。

直接套上述式子枚举$c_i$的情况乘上$n_i!$即可。

$$ \sum_{c_1…c_m,c_i\in[1,n_i]}\frac{(\sum c_i)!}{\prod(c_i)!}\prod_{i=1}^mn_i!(-1)^{n_i-c_i}\binom{n_i-1}{n_i-c_i} $$

令$s=\sum c_i$
$$ \sum_{c_1…c_m,c_i\in[1,n_i]}(-1)^{n-s}\frac{s!}{\prod(c_i)!}\prod_{i=1}^m\binom{n_i-1}{n_i-c_i} n_i! $$

同样的$DP$方程直接乘上$n_i!$即可。

$$ f[i][j]=\sum_{1\le k\le \min(n_i,j)} f[i-1][j-k]\times \frac{n_i!}{k!}\times\binom{n_i-1}{n_i-k} $$

#include <iostream>
#include <cmath>

namespace wxy{

#define int long long

const int N = 305,mod = 1e9 + 7;

int a[N],b[N],cnt[N],f[N][N],n,idx;

int fac[N],invfac[N];

inline void init(){
    fac[0]=invfac[0]=invfac[1]=1;
    for(int i=1;i<=n;i++)fac[i]=(long long)fac[i-1]*i%mod;
    for(int i=2;i<=n;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
    for(int i=2;i<=n;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
}

int C(int n,int m){return n<m?0:(long long)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}

inline bool sqr(int x){int S = sqrt(x);return S*S==x;}

inline int mul(int x,int y){return 1ll * x * y % mod;}

inline void main(){
    std::cin >> n; idx = 0;
    init();
    for (int i = 1; i <= n; i++){
        std::cin >> a[i]; b[i] = i;
        for (int j = 1; j < i; j++)
            if (sqr(a[i] * a[j])){b[i] = j; break;}
    }
    for (int i = 1; i <= n; i++){
        if (b[i] == i){
            ++idx;
            for (int j = 1; j <= n; j++)
                if (b[j] == i) cnt[idx]++;
        }
    }
    f[0][0] = 1; int v = 0;
    for (int i = 1; i <= idx; i++){
        v += cnt[i];
        for (int j = 1; j <= v; j++)
            for (int k = 1; k <= j && k <= cnt[i]; k++)
               f[i][j] = (f[i][j] + mul(fac[cnt[i]],mul(f[i-1][j-k],mul(C(cnt[i]-1,cnt[i]-k),invfac[k])))) % mod;
    }    
    int ans = 0;
    for (int i = 1; i <= n; i++){
        f[idx][i] = mul(f[idx][i],fac[i]);
        if ((n - i) % 2 == 1) ans = (ans + mod - f[idx][i]) % mod;
        else ans = (ans + f[idx][i]) % mod;
    }
    std::cout << ans;
}
}signed main(){wxy::main(); return 0;}