题解：AT_code_festival_2017_qualc_f Three Gluttons

· · 题解

考虑充要条件。但你直接对着这三个序列硬想是没有前途的，我们考虑增加一些信息创造入手点。

考虑已知三个人依次吃掉的寿司下标，令 m=\frac n3，记为 A_{i_1}\dots A_{i_m}，j,k 同理。首先不能存在相同元素，即每种寿司恰出现一次。接下来考虑轮到某个 A_{i_t} 时，它前面还存在一个 A_{k} 可以吃意味着什么，这等价于 B_{j_p}=A_k（或是 C）满足 j_p\le i_p。于是不难推出充要条件：

若已知吃掉的寿司，能否计算 C 序列剩下元素的填写方案？相当于已经满足了“对 A,B 序列的限制”，现在应满足“对 C 序列的限制”。由于吃掉的寿司恰为 [1,n]，于是等价于将 A_{i_t},B_{j_t} 填入 C 序列中，只需满足它们在 C_{k_t} 后面即可。经典套路倒推，容易得出方案数为 \prod\limits_{i=1}^m (3i-1)(3i-2)。

只需对吃掉的寿司计数。“A/B 寿司对 A/B 序列的限制”是好解决的。但是你显然不能让 C 寿司计入状态，因为难以处理互不相同这一点，同时 A/B 寿司就已经要开三维记录了。

考虑已知吃掉的 A/B 寿司，统计 C 寿司方案。考虑对 C_{k_t} 的限制：不能与 A_{i_{t+1}}\dots A_{i_m},B_{j_{t+1}}\dots B_{j_m},C_{k_{t+1}}\dots C_{k_m} 相同，不能出现在 A_{1\dots i_t},B_{1\dots j_t} 中。发现这两个限制不交，否则违反前面的充要条件。还是倒推，得出方案数 \prod\limits_{t=1}^m (3t-g_{i_t,j_t})，g_{x,y}=|A_{1\dots x}\cup B_{1\dots y}|。

预处理 g，大力 dp 记状态为 f_{a,b,t} 表示第 t 轮且 i_t=a,j_t=b，前缀和优化一下即可 O(1) 转移。O(n^3)。

总结：本题需灵活转换计数对象，增加或减少枚举信息。难以下手，便添加“吃掉的寿司”这一信息。后面发现难以直接记录 C 寿司到状态里，便放弃枚举而是直接计算方案。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 4e2 + 5, mod = 1e9 + 7;
int n, a[N], b[N], ap[N], bp[N], f[N][N], _f[N][N], g[N][N], buc[N];

signed main(){
    cin >> n;
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), ap[a[i]] = i;
    for(int i = 1; i <= n; ++i) scanf("%d", &b[i]), bp[b[i]] = i;
    if(a[1] == b[1]) {puts("0"); return 0;}
    for(int i = 1; i <= n; ++i){
        int ct = 0;
        for(int j = 1; j <= n; ++j) buc[j] = (ap[j] <= i), ct += buc[j];  
        for(int j = 1; j <= n; ++j) ct += (buc[b[j]] == 0), g[i][j] = ct;
    }
    f[1][1] = 1;
    for(int t = 2; t <= n / 3; ++t){
        for(int i = 1; i <= n; ++i)
            for(int j = 1, s = 0; j <= n; ++j){
                _f[i][j] = f[i][j]; 
                s = (s + f[i][j]) % mod;
                _f[i][j] = (_f[i - 1][j] + s) % mod; 
                f[i][j] = 0;
            }
        for(int i = t; i <= n; ++i)
            for(int j = t; j <= n; ++j){
                if(ap[b[j]] <= i || bp[a[i]] <= j) continue;
                if(g[i][j] < 3 * t) f[i][j] = 1ll * _f[i - 1][j - 1] * (3ll * t - g[i][j]) % mod;
            } 
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            ans = (ans + f[i][j]) % mod;
    for(int i = 1; i <= n / 3; ++i) ans = 1ll * ans * (3 * i - 1) * (3 * i - 2) % mod;
    cout << ans;
    return 0;
}