题解：CF2134F Permutation Oddness

· · 题解

CF2134F Permutation Oddness

Diff：*2900

有 4 种数，如果要直接 \mathrm{dp} 造出序列时间复杂度是 O(n^5) 的，无法接受。考虑挖掘一下 \mathrm{lowbit}(b_i,b_{i+1}) 的性质，注意到若 b_i=b_{i+1} 值是 0，如果组成 (0,2),(1,3) 则值为 2，其他情况都是 1。此处考虑一个染色的技巧，将 0,2 染成红色，1,3 染成蓝色，则原序列可以刻画成一个红蓝极长连续段交替的形式，这样不同连续段之间的贡献就是 1，同一连续段内相同数贡献是 0，不同数贡献是 2。我们发现这样似乎比较好做了，因为我们可以将红色和蓝色连续段分开算，然后最后对应超级拼装起来，那么只需思考如何对红色求出方案数，蓝色同理。

考虑定义 r(i,j) 表示红色连续段个数为 i，这些连续段内部的贡献为 j 的连续段方案数。只有异色，即交替才有贡献，先考虑一个连续段内部的情况。定义 f(i) 表示用 c_0 个 0，c_2 个 2 组成的、交替数量恰好为 i 的方案数，这是一个经典的组合计数，考虑相同数组成的连续段，如果有 j 个那么交替数量就是 j-1，那么交替数量为 i 等价于同数连续段有 k=i+1 个。交替，考虑对 k 奇偶分类：

记 F(n,m) 表示把 n 个相同数划分成 m 个连续段的方案数，用插板法得到 F(n,m)=\binom{n-1}{m-1}。

再将 k 变回 i，整理一下，得到：

f(2m)=\binom{c_0-1}{m}\binom{c_2-1}{m-1}+\binom{c_0-1}{m-1}\binom{c_2-1}{m} \\ f(2m-1)=2\binom{c_0-1}{m-1}\binom{c_2-1}{m-1}

那么考虑用 f 计算 r，枚举 j 表示要划分有 j 个异色相邻的序列，其方案数对应 f(j)，划分时如果切开了两个相同色的则是没有贡献的，如果切开异色的则贡献为 -2，于是枚举 k 表示有多少个切到了异色位置，选择方案数是 \binom{j}{k}，对于同色部分可以随便放，总共有 c_0+c_2-1 个位置，j 个是异色的，则有 (c_0+c_2-1-j) 个同色，划分成 i 段有 (i-1) 个划分位置，划分异色用了 k 个，则有 (i-1-k) 个用于划分异色，因此方案数为 \binom{c_0+c_2-1-j}{i-1-k}，综上得到：

r_{i,2(j-k)}\leftarrow f_j\times \binom{j}{k}\binom{c_0+c_2-1-j}{i-1-k}

同理可以计算出 b(i,j) 表示蓝色信息。接着就要用 r_{i,j} 拼装得到 ans，枚举 i_r,i_b 分别表示红、蓝连续段的个数，不难发现此时有 i_b\in [i_r-1,i_r+1]，这一部分的贡献就是连续段相接的部分，即 (i_r+i_b-1)，再枚举 j_r,j_b 表示红蓝内部的贡献，拼接时再对开头方案数讨论，易得：

ans_{i_r+i_b-1+j_r+j_b}\leftarrow (1+[i_r=i_b])\cdot r(i_r,j_r)\times b(i_b,j_b)

时间复杂度是 O(n^3)，可以通过。

:::info[代码]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod=1e9+7;
inline int Mod(int x) { return x<0 ? x+mod : (x>=mod ? x-mod : x); }
inline void adm(int &x,int y) { x=Mod(x+y); }
inline int qmi(ll a,int b)
{
    ll res=1;
    for (;b;b>>=1,a=a*a%mod) if (b&1) res=res*a%mod;
    return res;
}
const int N=810;
int fac[N],infac[N];
void init(int M=N-1)
{
    fac[0]=1; for (int i=1;i<=M;i++) fac[i]=(ll)fac[i-1]*i%mod;
    infac[M]=qmi(fac[M],mod-2); for (int i=M-1;~i;i--) infac[i]=(ll)infac[i+1]*(i+1)%mod;
}
int binom(int a,int b)
{
    if (a<0 || b<0 || a<b) return 0;
    return (ll)fac[a]*infac[b]%mod*infac[a-b]%mod;
}
int c0,c1,c2,c3;
int f[N<<1],r[N][N<<1],b[N][N<<1];
int ans[N<<1];

void work(int x,int y,int g[N][N<<1])
{
    memset(f,0,sizeof(f)); 
    for (int m=1;2*m-1<=(x+y)*2;m++)
    {
        f[m*2]=Mod((ll)binom(x-1,m)*binom(y-1,m-1)%mod+(ll)binom(x-1,m-1)*binom(y-1,m)%mod);
        f[m*2-1]=2ll*binom(x-1,m-1)*binom(y-1,m-1)%mod;
    }
    for (int i=1;i<=x+y;i++)
    {
        for (int j=0;j<=x+y;j++)
        {
            for (int k=0;k<=j && k<=i-1;k++)
            {
                int coef=(ll)binom(j,k)*binom(x+y-1-j,i-1-k)%mod;
                adm(g[i][2*(j-k)],(ll)coef*f[j]%mod);
            }
        }
    }
}

void solve()
{
    cin >> c0 >> c1 >> c2 >> c3;
    memset(r,0,sizeof(r)); work(c0,c2,r); 
    memset(b,0,sizeof(b)); work(c1,c3,b);

    int n=c0+c1+c2+c3;
    for (int i=0;i<2*n-1;i++) ans[i]=0;
    for (int ir=1;ir<=c0+c2;ir++)
    {
        for (int ib=ir-1;ib<=ir+1;ib++)
        {
            if (ib<1 || ib>c1+c3) continue;
            for (int jr=0;jr<=2*(c0+c2);jr+=2)
            {
                for (int jb=0;jb<=2*(c1+c3);jb+=2)
                {
                    int coef=1+(ir==ib);
                    adm(ans[ir+ib-1+jr+jb],(ll)coef*r[ir][jr]*b[ib][jb]%mod);
                }
            }
        }
    }
    for (int i=0;i<2*n-1;i++) cout << ans[i] << " ";
    cout << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    init();
    int T; cin >> T;
    while (T--) solve();

    return 0;
}

:::