小红的数组回文值

题目描述

小红定义一个数组的回文值是：修改最少数量的元素值得该数组回文，这个次数即数组的回文值。

例如，${3,2,4,3}$ 的回文值是 $1$，只需要将第二个元素修改为 $4$ 即可。

现在小红拿到了一个数组，她希望你求出所有子序列的回文值之和。你能帮帮她吗？

定义子序列为从数组中从左到右取出若干个元素（可以不取、可以全取、可以不连续）形成的数组。

输入描述:

第一行输入一个整数 $n(1 \leq n \leq 2000)$ 代表数组中的元素数量。

第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i  \leq 10^9)$ 代表数组元素。

输出描述:

在一行上输出一个整数，代表所有子序列的回文值之和。由于答案可能很大，请将答案对 $(10^9 +7)$ 取模后输出。

示例1

输入

3
1 2 3

输出

4

说明

${1,2}$、${1,3}$、${2,3}$ 和 ${1,2,3}$ 的回文值都是 $1$。其余子序列的回文值均为 $0$。

示例2

输入

4
999 999 999 999

输出

0

解题思路

  比赛的时候不知道范德蒙德卷积，只能写暴力骗点分了。

  对于这种计数类问题可以先考虑贡献法。对于任意两个满足 $i < j$ 且 $a_i \ne a_j$ 的元素，显然在以 $a_i$ 和 $a_j$ 为对称元素的子序列中，因为 $a_i \ne a_j$ 所以会产生 $1$ 的贡献，因此 $a_i$ 和 $a_j$ 对答案的贡献就是满足这样要求的子序列的数量。

  先假设 $a_i$ 和 $a_j$ 在子序列中就是对称的元素，首先对于 $a_{i+1} \sim a_{j-1}$ 中的元素可以任意选择，不会改变 $a_i$ 和 $a_j$ 的对称性，有 $2^{j-i-1}$ 种方案。然后考虑左边 $a_{1} \sim a_{i-1}$ 和右边 $a_{j+1} \sim a_{n}$ 的选择，显然两边应该选择同等数量的元素，那么可选的方案数量为 $\sum\limits_{k=0}^{\min\{i-1, n-j\}}{C_{i-1}^{k} \cdot C_{n-j}^{k}}$。因此以 $a_i$ 和 $a_j$ 为对称元素的子序列的数量就是 $2^{j-i-1} \cdot \sum\limits_{k=0}^{\min\{i-1, n-j\}}{C_{i-1}^{k} \cdot C_{n-j}^{k}}$。

  最后总的答案就是$$\sum\limits_{i=1}^{n}{\sum\limits_{j=i+1}^{n}{[a_i \ne a_j] \left( 2^{j-i-1} \cdot \sum\limits_{k=0}^{\min\{i-1, j-n\}}{C_{i-1}^{k} \cdot C_{j-n}^{k}} \right)}}$$

  如果直接暴力计算 $\sum\limits_{k=0}^{\min\{i-1, n-j\}}{C_{i-1}^{k} \cdot C_{n-j}^{k}}$ 那么总的时间复杂度为 $O(n^3)$，显然会超时。事实上该组合式可以由范德蒙德卷积推导出 $\sum\limits_{k=0}^{\min\{i-1, n-j\}}{C_{i-1}^{k} \cdot C_{n-j}^{k}}= C_{i-1+n-j}^{i-1}$。

  首先有范德蒙德卷积 $\sum\limits_{i=0}^{k}{C_{n}^{i} \cdot C_{m}^{k-i}} = C_{n+m}^{k}$，具体证明可以参考链接。从组合意义上来讲的话，原本从大小为 $n+m$ 的集合中选出 $k$ 个元素，等价于把集合分别划分为大小为 $n$ 的集合与大小为 $m$ 的集合，先从大小为 $n$ 的集合中取出 $i \, (0 \leq i \leq k)$ 个元素，再从大小为 $m$ 的集合中取出 $k-i$ 个元素。

  现在假设 $k = m$，那么有 $\sum\limits_{i=0}^{m}{C_{n}^{i} \cdot C_{m}^{m-i}} = \sum\limits_{i=0}^{m}{C_{n}^{i} \cdot C_{m}^{i}} = C_{n+m}^{m} = C_{n+m}^{n}$。

  AC 代码如下，时间复杂度为 $O(n^2)$：

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

typedef long long LL;

const int N = 2005, mod = 1e9 + 7;

int a[N];
int c[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        int p = 1;
        for (int j = i + 1; j <= n; j++) {
            if (a[i] != a[j]) ret = (ret + 1ll * p * c[i - 1 + n - j][i - 1]) % mod;
            p = 2ll * p % mod;
        }
    }
    cout << ret;
    
    return 0;
}

参考资料

  题解 | #周赛59题解#：https://www.nowcoder.com/discuss/662403130013868032

  范德蒙德卷积 - OI Wiki：https://oi-wiki.org/math/combinatorics/vandermonde-convolution/