题解 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\}$ 数组。则，该吃寿司方案合法（也即喜好序列合法），当且仅当： - $\{a_i\},\{b_j\},\{c_k\}$ 数组中无相同元素。 - 对于每个 $t$，$a_{i_t}$ 仅在 $\{a_1\sim a_{i_t}\}\cup\{b_1\sim b_{j_t}\}\cup\{c_1\sim c_{k_t}\}$ 序列中出现一次。$b_{j_t},c_{k_t}$ 同理须满足此条件。（因为不然要么他们会有矛盾，要么就会更早被抢先吃掉） 现在考虑不知道 C 的喜好序列。则此时 $\{c_k\}$ 便退化了（因为我们不知道 $c$ 数组，进而不知道其吃掉的每个寿司在 $c$ 中的位置），退化成其依次吃了哪个寿司的数组 $\{x\}$。如果能从 $\{x\}$ 反推出任一 $c$，依照我们一开始的推断，其必存在且仅存在 $\prod\limits_{i=1}^n(3i-2)(3i-1)$ 种不同的 $c$。于是我们现在考虑判断有无与 $x$ 对应的 $c$。 其有，当且仅当： - 无相同元素。 - $a_{i_t}$ 仅在 $\{a_1\sim a_{i_t}\}\cup\{b_1\sim b_{j_t}\}$ 中出现一次，$b_{j_t}$ 同理。 - $x_t$ 未在 $\{a_1\sim a_{i_t}\}\cup\{b_1\sim b_{j_t}\}$ 中出现。 于是我们可以用上述条件来验证一个寿司序列是否合法。 考虑当前填到了 $x$ 序列的第 $t$ 个位置。则，如下数不能填入 $x_t$： - $t'\in[t+1,n]$ 时的 $a_{i_{t'}},b_{j_{t'}},x_{t'}$。 - $\{a_1\sim a_{i_t}\}\cup\{b_1\sim b_{j_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的时候要注意判定限制的第二条。 代码： ```cpp #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; } ```