题解 AT3593 【Three Gluttons】

· · 题解

首先先将 n 除以 3，得到每个人吃的寿司数。

考虑倒序思考。设三个人最后一个分别吃了 x,y,z 三个寿司，则其对于 C 的排列有何限制？

显然，在 C 的排列中，x,y 须在 z 之后，不然 C 就不会去吃 z 了（我们不需要管 AB 两人的序列中 z 与 x,y 的关系，因为我们现在做的是从三个人吃东西的序列反推出 C 的喜好序列，所以我们考虑到的 x,y,z 一定存在至少一个 C 的排列满足这种情况，不然我们也不会考虑它）。顺序要么是 zxy 要么是 zyx，共 2 种。

现在，我们让时间回溯一格。在吃倒数第二个寿司时，限制仍是唯一的，即 C 吃的寿司在本回合中是他最喜欢的。不需要考虑 AB 这回合吃的寿司与下回合的 x,y 间的关系，因为反正这回合中都被吃掉了，即使 C 比起 x,y 更喜欢它们也没机会了。于是，第一个寿司共有 4 个位置可以放，即除了开头外的任何位置。第二个寿司共有 5 个位置可以放。

继续回溯的话，会发现倒数第 i 次的两个寿司的方案数分别是 3i-2,3i-1。于是对于任一合法的 ABC 吃寿司的序列，总对应着 \prod\limits_{i=1}^n(3i-2)(3i-1) 种合法的序列，且此方案数与具体的寿司序列并无关系，可以最后一并乘上。于是问题转换为求合法的 ABC 吃寿司的序列数。

现在考虑当 ABC 喜好序列固定时如何判断其会不会冲突。我们考虑令 a_{i_1},a_{i_2},a_{i_3},\dots,a_{i_n} 表示 A 吃的寿司。同理，我们得到了 \{b_j\} 与 \{c_k\} 数组。则，该吃寿司方案合法（也即喜好序列合法），当且仅当：

现在考虑不知道 C 的喜好序列。则此时 \{c_k\} 便退化了（因为我们不知道 c 数组，进而不知道其吃掉的每个寿司在 c 中的位置），退化成其依次吃了哪个寿司的数组 \{x\}。如果能从 \{x\} 反推出任一 c，依照我们一开始的推断，其必存在且仅存在 \prod\limits_{i=1}^n(3i-2)(3i-1) 种不同的 c。于是我们现在考虑判断有无与 x 对应的 c。

其有，当且仅当：

于是我们可以用上述条件来验证一个寿司序列是否合法。

考虑当前填到了 x 序列的第 t 个位置。则，如下数不能填入 x_t：

二者无交，则其余 3t-|\{a_1\sim a_{i_t}\}\cup\{b_1\sim b_{j_t}\}| 个数均可。

于是我们设 f_{i,j,t} 表示 i_t=i,j_t=j 时的方案数。直接 DP 即可。DP 的时候需要用前缀和记录所有 i_t\leq i,j_t\leq j 的 DP 状态之和，这样就能做到 O(1) 转移。

DP的时候要注意判定限制的第二条。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a[410],b[410],f[410][410][410],g[410][410],res;
bool occ[410],oa[410][410],ob[410][410];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++){
        occ[a[i]]=true;
        g[i][0]=i;
        for(int j=1;j<=n;j++)g[i][j]=g[i][j-1]+!occ[b[j]];
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)oa[i][a[j]]=true,ob[i][b[j]]=true;
//  for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",g[i][j]);puts("");}
    n/=3;
    for(int i=0;i<=3*n;i++)for(int j=0;j<=3*n;j++)f[0][i][j]=1;
    for(int t=1;t<=n;t++)for(int i=t;i<=3*n;i++)for(int j=t;j<=3*n;j++){
        if(!ob[j][a[i]]&&!oa[i][b[j]])f[t][i][j]=1ll*f[t-1][i-1][j-1]*(3*t-g[i][j])%mod;
        f[t][i][j]=(0ll+f[t][i][j]+f[t][i-1][j]+f[t][i][j-1]+mod-f[t][i-1][j-1])%mod;
    }
    res=f[n][3*n][3*n];
    for(int i=1;i<=n;i++)res=1ll*res*(3*i-2)*(3*i-1)%mod;
    printf("%d\n",res);
    return 0;
}