题解：P9385 [THUPC 2023 决赛] 阴阳阵法

· · 题解

摘抄了 chrhaa 的题解，做了一些详细说明。

初步想法和 Aleph1022 或者 EI 的思路差不多，解两个 \exp 方程。

但是我不会而且模数非素，感觉会处理不好奇怪的地方。

类似 Fast as Fast as Ryser，这种一大坨的数学题，往往有组合意义 dp 牛牛做法。

考虑不合法的基环树要求：环上黑白点都是奇数。直接对这个条件容斥看着不错。

记 n,m 的答案为 f_{n,m}。初始有 f_{i,0}=(n+m)^i。

每次我们加入一个黑点，这个点有 n 种连法：f_{i,j}\gets nf_{i,j-1}。

接下来容斥掉，新加的黑点构成不合法基环树的情况：

f_{i,j}=nf_{i,j-1}-\sum\limits_{x\in [1,j],y\in[1,i],2\nmid xy}\dbinom{j-1}{x-1}\dbinom{i}{y}\dbinom{y}{x}(y-1)!x!f_{i-y,j-x}

从 i,j-1 个白/黑点种选择 y,x-1 个构成 不合法基环树的环。

然后考虑钦定任意一白点作为环头，黑点间插入白点，贡献自然是 \dbinom{y}{x}(y-1)!x!。

唯一的问题是此时复杂度是 \mathcal{O}(n^4) 的，无法通过。

:::info[示例代码]

for(int i=0;i<=n;i++)
{
    *f[i]=ksm(n+m,i);
    for(int j=1;j<=m;j++)
    {
        f[i][j]=1ll*f[i][j-1]*n%P;
        for(int x=1;x<=j;x+=2) for(int y=x;y<=i;y+=2)
            f[i][j]=(f[i][j]+
            1ll*(P-C[j-1][x-1])*C[i][y]%P*C[y][x]%P*jc[y-1]%P*jc[x]%P*f[i-y][j-x])%P;
    }
}

:::

后面那一坨肯定能拆组合数分奇偶做递推，但是太难了，开始考虑组合意义搞掉后面部分。

考虑 辅助数组交替转移 dp 的思想，建立辅助数组 g 处理不合法基环树。

则 $f$ 的转移变成 $f_{i,j}=nf_{i,j-1}-g_{i,j-1,1,0,0}$。 转移完 $f_{i,*}$，考虑根据现有的 $f_{i,*},g_{i,*}$ 求出 $g_{i+1,*}$。 - 首先 $f$ 有贡献 $g_{i+1,j,1,0,0}\gets (i+1)f_{i,j}$，表示开始一个环。 - 然后就是 $g$ 内部的贡献。 - 加白点：$g_{i+1,j,x\oplus 1,y,0}\gets (i+1)(g_{i,j,x,y,0}+g_{i,j,x,y,1})

以上。复杂度 \mathcal{O}(n^2)，常数还好，跑得挺快。

这题主要学习 辅助数组交替转移 dp 的思想。

有些地方钦定白点可以变成钦定黑点，没那么严格，只是贡献需要自己重新算。看看你自己想怎么写了。

:::info[代码]

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2005;
int n,m,mod,C[N][N],jc[N],f[N][N],g[N][N][2][2][2];
inline void ad(int &x,int y){(x+=y)>=mod&&(x-=mod);}
inline void ad(int &x,LL y){x=(x+y)%mod;}
inline int ksm(int x,int p){int s=1;for(;p;(p&1)&&(s=(LL)s*x%mod),x=(LL)x*x%mod,p>>=1);return s;}
int main()
{
    cin.tie(0)->sync_with_stdio(0);cin>>n>>m>>mod;
    for(int i=*jc=1;i<=n;i++) jc[i]=(LL)jc[i-1]*i%mod;
    for(int i=*C[0]=1;i<=max(n,m);i++) for(int j=*C[i]=1;j<=i;j++)
        ad(C[i][j]=C[i-1][j],C[i-1][j-1]);
    for(int i=0;i<=n;i++){
        *f[i]=ksm(n+m,i);
        for(int j=1;j<=m;j++) f[i][j]=((LL)f[i][j-1]*n+mod-g[i][j-1][1][0][0])%mod;
        for(int j=0;j<=m;j++){
            ad(g[i+1][j][1][0][0],(LL)f[i][j]*(i+1));
            for(int o:{0,1}) for(int p:{0,1})
                ad(g[i+1][j][o^1][p][0],(LL)(g[i][j][o][p][0]+g[i][j][o][p][1])*(i+1)),
                ad(g[i][j+1][o][p^1][1],(LL)g[i][j][o][p][0]*(j+1));
        }
    }
    return cout<<f[n][m],0;
}

:::