题解：P16906 [CCO 2026] Walking on a Graph

dxw2306 · 2026-11-11 10:45:41 · 题解

题意转化与状态定义

题目比较难懂，先考虑转换题意，发现合法路径满足以下条件：

因为注意到节点 1 和节点 2 的转换和数量是没有限制的，所以问题就转换成了求合法的「编号 3 \sim n 中若干个点」的序列数量。

我们设 f_{i,a,b,c,d} 表示处理完编号 3 \sim i 的节点后，已选点构成 a 条白到白、b 条白到黑、c 条黑到白、d 条黑到黑的合法方案数。接下来根据插入 DP 的经典转移方式转移（不熟悉的同学可以参考 P5999 [CEOI 2016] kangaroo）。

下面给出黑点的转移：

• 单开一段：

  f_{i,a,b,c,d} \gets f_{i-1,a,b,c,d-1}

• 把当前点接在某一段开头：

  f_{i,a,b,c,d} \gets f_{i-1,a,b,c,d} \times (c+d)

• 把当前点接在某一段末尾：

  f_{i,a,b,c,d} \gets f_{i-1,a+1,b-1,c,d} \times (a+1) + f_{i-1,a,b,c+1,d-1} \times (c+1)

• 用当前点合并两段：

  \begin{aligned} f_{i,a,b,c,d} &\gets f_{i-1,a,b,c+1,d} \times (c+1) \times a \\ f_{i,a,b,c,d} &\gets f_{i-1,a+1,b-1,c,d+1} \times (a+1) \times (d+1) \\ f_{i,a,b,c,d} &\gets f_{i-1,a,b,c+1,d} \times (c+1) \times d \\ f_{i,a,b,c,d} &\gets f_{i-1,a,b,c+1,d} \times (c+1) \times c \end{aligned}

• 不把当前节点加入序列：

  f_{i,a,b,c,d} \gets f_{i-1,a,b,c,d}

白色点同理。

答案统计

上述状态中，黑到黑的段无法贡献到答案，同时白到白的段并没有定向，因此

其中 a,b,c \geq 0。

参考实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int mx=52;
int n;
char col[mx];
int f[2][mx][mx][mx][mx];
int fread()
{
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*w;
}
int fac[mx];
int ksm(int x,int y)
{
    int ans=1;
    while(y)
    {
        if(y&1) ans*=x,ans%=mod;
        x*=x,x%=mod;
        y>>=1;
    }
    return ans;
}
signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n=fread();
    for(int i=1;i<=n;i++) cin>>col[i];
    f[0][0][0][0][0]=1;
    for(int i=3;i<=n;i++)
    {
        int o=(i&1);
        memset(f[o],0,sizeof(f[o]));
        for(int a=0;a<=i;a++)
        {
            for(int b=0;a+b<=i;b++)
            {
                for(int c=0;a+b+c<=i;c++)
                {
                    for(int d=0;a+b+c+d<=i;d++)
                    {
                        if(col[i]=='B')
                        {
                            if(d!=0) f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c][d-1])%mod;
                            f[o][a][b][c][d]=(f[o^1][a][b][c][d]*(c+d)%mod+f[o][a][b][c][d])%mod;
                            if(b!=0) f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a+1][b-1][c][d]*(a+1)%mod)%mod;
                            if(d!=0) f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c+1][d-1]*(c+1))%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c+1][d]*(c+1)%mod*a%mod)%mod;
                            if(b!=0) f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a+1][b-1][c][d+1]*(a+1)%mod*(d+1)%mod)%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c+1][d]*(c+1)%mod*d%mod)%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c+1][d]*(c+1)%mod*c%mod)%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c][d])%mod;
                        }
                        else
                        {
                            if(a!=0) f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a-1][b][c][d])%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c][d]*(a+b)%mod)%mod;
                            if(a!=0) f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a-1][b+1][c][d]*(b+1)%mod)%mod;
                            if(c!=0) f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c-1][d+1]*(d+1)%mod)%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b+1][c][d]*a%mod*(b+1)%mod)%mod;
                            if(c!=0) f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a+1][b][c-1][d+1]*(a+1)%mod*(d+1)%mod)%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b+1][c][d]*(b+1)%mod*b%mod)%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b+1][c][d]*(b+1)%mod*d%mod)%mod;
                            f[o][a][b][c][d]=(f[o][a][b][c][d]+f[o^1][a][b][c][d])%mod;
                        }
                    }
                }
            }
        }
    }
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    int ans=0;
    for(int a=0;a<=n;a++)
    {
        for(int b=0;a+b<=n;b++)
        {
            for(int c=0;a+b+c<=n;c++)
            {
                ans+=f[n&1][a][b][c][0]*ksm(2,a)%mod*fac[a+b+c]%mod;
                ans%=mod;
            }
        }
    }
    cout<<ans;
    return 0;
}

本文排版使用 Hy4 辅助实现