P10366 [PA2024] Bardzo Ulubiony Ciąg 题解

· · 题解

0. 前言

作为一道计数/优化枚举的题目，本题比 [NOIP2022] 种花 难不少，思维难度较大。

本题主要考察的知识点：前缀和、容斥、枚举。

1. 大致思路

（注：为了方便计算，接下来先抛去题目中 i<j<k 的条件，最后输出时除以 3! 即可。）

首先不考虑 “3 个区间互不相同” 的条件（即区间可以重复），设方案数为 A。

接着考虑 a 种总方案中，有多少种是不合法的（存在重复区间）。

第一类：三个区间均相同，设情况数为 B。

第二类：两个区间相同，第三个区间不同，设情况数为 C。

则最终答案为 (A-B-C)/3!。

2. 具体实现

先对数列 a 做前缀和 s，这样可以做到 O(1) 查询区间和。

下文设第 i,j,k 个区间的和分别为 t_1, t_2, t_3。

计算 B：

由于三个区间全部相同，所以 t_1=t_2=t_3 且 t_1+t_2+t_3=0，易得 t_1=t_2=t_3=0。

所以只需要统计 a 数列有多少个子区间的和为 0 即可，容易实现：

for(int l = 1; l <= n; l++)
    for(int r = l; r <= n; r++)
        cnt[a[r] - a[l - 1] + mv]++;
B = cnt[mv];

（注：代码中的变量名等会在文章最后有解释，可先去看，再回来理解该段代码）。

计算 C：

不失一般性的，假设 i=j，则易得 t_1=t_2。

则由此可得 t_3 = 0-t_1-t_2=-2\cdot t_1。

所以只需要枚举和为 t_1（或 t_2）的区间，再用一个桶统计第三个区间的方案数即可，给出这部分的代码：

for(int l = 1; l <= n; l++){
    for(int r = l; r <= n; r++){
        int sum = a[r] - a[l - 1];
        if(sum == 0) C += cnt[mv] - 1;
        else C += cnt[-2 * sum + mv];
    }
}
C *= 3;

Q1：当 t_1=t_2=0 时，为什么方案数是 cnt_0-1？

A1：因为其中有 “三段区间均相同” 的一种情况，而该情况在 B 中已经统计过了，所以在这里要把它去掉。

Q2：那为什么 t_1 \ne 0 时，就不存在这种重复计算的可能呢：

A2：此时 t_3=-2 \cdot t_1\ne t_1，区间和都不相等，区间编号就更不可能相等啦~

Q3：为什么最后 C 要乘以 3？

A3：在开头我们假设了 i=j。但实际上还有 i=k 和 j=k 这两种情况。

计算 A：

本题中最难，也是最巧妙的地方（前方高能！）。

不难想到枚举前两个区间，再根据 t_3=-(t_1+t_2) 算出第三个区间的和，用桶加以统计。但是这样做的时间复杂度为 O(n^4)，需要优化。

这里给出教练 noip_1 的一种奇妙思路：

memset(cnt, 0, sizeof cnt);
for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++)
        for(int k = j; k <= n; k++)
            cnt[a[k] - a[j - 1] - a[i - 1] + mv]++;
    for(int j = 1; j <= n; j++)
        for(int k = j; k <= n; k++)
            A += cnt[-(a[k] - a[j - 1] + a[i]) + mv];
}

以下记三个区间分别为 [l_1, r_1], [l_2, r_2], [l_3, r_3]。

回到题目本身：这三个区间要满足 t_1+t_2+t_3=0。把等式稍微变形一下：

t_1+t_2+t_3=0 \downarrow (s_{r_1} - s_{l_1-1})+(s_{r_2}-s_{l_2-1})+(s_{r_3} - s_{l_3-1})=0 \downarrow -(s_{r_1}-s_{l_1-1}+s_{r_2})=s_{r_3}-s_{l_3-1}-s_{l_2-1}

现在懂了吧！上面的代码所做的工作就是：将等式右边的 s_{r_3}-s_{l_3-1}-s_{l_2-1} 存入桶中，然后枚举等式左边的 l_1,r_1,r_2，根据等式进行匹配计数。时间复杂度能做到 O(n^3)。

回顾一下暴力做法：将 t_1+t_2 存入桶的时间复杂度为 O(n^4)，枚举 t_3 的时间复杂度为 O(n^2)。由于没有平衡好两者的关系，所以时间复杂度较高。

3. 代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 505, V = 4e7 + 5, mv = 2e7;
int n, a[N], cnt[V];
ll A, B, C, ans;
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i], a[i] += a[i - 1];

    for(int l = 1; l <= n; l++)
        for(int r = l; r <= n; r++)
            cnt[a[r] - a[l - 1] + mv]++;
    B = cnt[mv];
    for(int l = 1; l <= n; l++){
        for(int r = l; r <= n; r++){
            int sum = a[r] - a[l - 1];
            if(sum == 0) C += cnt[mv] - 1;
            else C += cnt[-2 * sum + mv];
        }
    }
    C *= 3;
    memset(cnt, 0, sizeof cnt);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            for(int k = j; k <= n; k++)
                cnt[a[k] - a[j - 1] - a[i - 1] + mv]++;
        for(int j = 1; j <= n; j++)
            for(int k = j; k <= n; k++)
                A += cnt[-(a[k] - a[j - 1] + a[i]) + mv];
    }
    ans = (A - B - C) / 6;
    cout << ans;
    return 0;
}

注：

4. 后记

这里 是我整理的此类题型的题单，持续更新中，大家有好题也可以在评论区推荐给我。

如果您觉得这篇题解对您有帮助的话，请点个赞，感谢 qwq。