专栏文章

题解：AT_code_festival_2017_qualc_f Three Gluttons

__Cheems
AT_code_festival_2017_qualc_f题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minjv12p
此快照首次捕获于
2025/12/02 03:36
3 个月前
此快照最后确认于
2025/12/02 03:36
3 个月前
查看原文
考虑充要条件。但你直接对着这三个序列硬想是没有前途的，我们考虑增加一些信息创造入手点。
考虑已知三个人依次吃掉的寿司下标，令 m=n3m=\frac n3，记为 Ai1…AimA_{i_1}\dots A_{i_m}，j,kj,k 同理。首先不能存在相同元素，即每种寿司恰出现一次。接下来考虑轮到某个 AitA_{i_t} 时，它前面还存在一个 AkA_{k} 可以吃意味着什么，这等价于 Bjp=AkB_{j_p}=A_k（或是 CC）满足 jp≤ipj_p\le i_p。于是不难推出充要条件：
  • 对任意 iti_t，AitA_{i_t} 在 B1…jtB_{1\dots j_t} 和 C1…ktC_{1\dots k_t} 中没有出现过。我们称该限制为“AA 寿司对 B/CB/C 序列的限制”。Bj,CkB_j,C_k 同理。
若已知吃掉的寿司，能否计算 CC 序列剩下元素的填写方案？相当于已经满足了“对 A,BA,B 序列的限制”，现在应满足“对 CC 序列的限制”。由于吃掉的寿司恰为 [1,n][1,n]，于是等价于将 Ait,BjtA_{i_t},B_{j_t} 填入 CC 序列中，只需满足它们在 CktC_{k_t} 后面即可。经典套路倒推，容易得出方案数为 ∏i=1m(3i−1)(3i−2)\prod\limits_{i=1}^m (3i-1)(3i-2)。
只需对吃掉的寿司计数。“A/BA/B 寿司对 A/BA/B 序列的限制”是好解决的。但是你显然不能让 CC 寿司计入状态，因为难以处理互不相同这一点，同时 A/BA/B 寿司就已经要开三维记录了。
考虑已知吃掉的 A/BA/B 寿司，统计 CC 寿司方案。考虑对 CktC_{k_t} 的限制：不能与 Ait+1…Aim,Bjt+1…Bjm,Ckt+1…CkmA_{i_{t+1}}\dots A_{i_m},B_{j_{t+1}}\dots B_{j_m},C_{k_{t+1}}\dots C_{k_m} 相同，不能出现在 A1…it,B1…jtA_{1\dots i_t},B_{1\dots j_t} 中。发现这两个限制不交，否则违反前面的充要条件。还是倒推，得出方案数 ∏t=1m(3t−git,jt)\prod\limits_{t=1}^m (3t-g_{i_t,j_t})，gx,y=∣A1…x∪B1…y∣g_{x,y}=|A_{1\dots x}\cup B_{1\dots y}|。
预处理 gg，大力 dp 记状态为 fa,b,tf_{a,b,t} 表示第 tt 轮且 it=a,jt=bi_t=a,j_t=b，前缀和优化一下即可 O(1)O(1) 转移。O(n3)O(n^3)。
总结：本题需灵活转换计数对象，增加或减少枚举信息。难以下手，便添加“吃掉的寿司”这一信息。后面发现难以直接记录 CC 寿司到状态里，便放弃枚举而是直接计算方案。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...