题解：CF1188C Array Beauty

· · 题解

这题我的想法倒是挺一波三折的——从想到一个会 T 的方法到发现如何优化这个方法。

首先，我们需要发现这是一道传统的拆贡献题——如果一个长度为 k 序列的美丽值是 x，那么我们会对于所有正整数 t，统计美丽值 \ge t 的序列数量并把它加到答案里。这样一个序列最终就会为答案刚刚好好贡献 x。

第一步肯定要对序列排好序，由于仅要求是子序列，所以打乱顺序不会对答案产生影响。接下来问题转化为对于所有正整数 t，求美丽值 \ge t 的长度为 k 的序列数量，也即相邻两项差值均 \ge t 的长度为 k 的序列数量。

这个比较简单：设 R_i 表示第一个位置 x 使得 a_x-a_i\ge t（如果不存在则为 n+1），那么我们可以初始设 R_i=i，然后在升序遍历 t 时可以对于每个位置从 R_i 继续往后扫描——直到扫到满足条件的为止，来以总时间复杂度 O(n^2) 处理出来。

然后设 f_{i,j} 表示第一项为原序列的第 i 个位置且序列长度为 j 的序列数量，则有：

f_{i,1}=1,\forall 2\le j\le k,f_{i,j}=\sum_{y=R_i}^n f_{y,j-1}

明显，我们倒着处理 dp 值时可以使用后缀和优化。于是对于单个 t，它的时间复杂度就是 O(nk)。

最后我们想想我们要把 t 处理到哪？明显，t 最多处理到值域上界 A_{\max}=10^5，但是这样时间复杂度就是 O(A_{\max}nk+n^2)，爆炸了。

但是，t 真的要处理到 A_{\max} 吗？做到这里的时候我又灵光一现：如果 (k-1)t>A_{\max}，那么这个序列的第一项和最后一项差值便会大于 A_{\max}，这就矛盾了！

这样我们 t 处理到 \lfloor\frac{A_{\max}}{k-1}\rfloor 即可！时间复杂度即为 O(\frac{A_{\max}}{k-1}nk+n^2)=O(A_{\max}n+n^2)，成功通过。

代码：

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

int n,K,a[1005],nxt[1005],dp[1005][1005],pres[1005][1005],ans;
const int modp=998244353;

int main(){
    cin>>n>>K;for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);for(int i=1;i<=n;i++)nxt[i]=i+1;
    for(int o=1;o<=100000/(K-1);o++){
        for(int i=1;i<=n;i++)while(nxt[i]<=n&&a[nxt[i]]-a[i]<o)nxt[i]++;
        for(int i=n;i>=1;i--){
            dp[i][1]=1;for(int j=2;j<=K;j++)dp[i][j]=pres[nxt[i]][j-1];
            for(int j=1;j<=K;j++)pres[i][j]=(pres[i+1][j]+dp[i][j])%modp;
        }
        ans=(ans+pres[1][K])%modp;
    }
    cout<<ans;
    return 0;
}