2023“钉耙编程”联赛 Day 3 E 题

2023“钉耙编程”联赛 Day 3 E 题

原题描述

题面由我校翻译组激情制造。

有一个云服务 API text{API} API 来帮助用户存储历史时间戳。

每个用户的数据结构最初是一个空堆栈。

每次向 API text{API} API 发送带有整数 x x x (表示当前时间戳)的请求时，服务器都会将 x x x 附加到堆栈的末尾。

若 x x x 小于堆栈中存储的前一个时间戳时，服务器将认为输入是错误的，将加入前一个时间戳入堆栈而不是 x x x。

您已经发布了 n n n 次 API text{API} API，您的请求时间戳在第 i i i 次调用中是 x i x_i xi​。

然而，网络已经失控。

服务器可能以任意顺序接收您的请求，甚至可能错过某些请求。

知道了这个问题，您要求随叫随到的工程师查看数据库中的堆栈。

假设服务器正好收到 k k k 个请求，那么它可能有多少不同的堆栈?

输入格式

第一行包含单个整数 T T T ( 1 ≤ T ≤ 100 ) (1≤T≤100) (1≤T≤100)，测试用例的数量。对于每个测试用例:

输入的第一行包含单个整数 n n n ( 1 ≤ n ≤ 3000 ) (1≤n≤3000) (1≤n≤3000)，表示请求总数。

第二行包含 n n n 个整数 x 1 , x 2 , … , x n x_1,x_2,dots,x_n x1​,x2​,…,xn​ ( 1 ≤ x i ≤ 1 0 9 ) (1≤x_i≤10^9) (1≤xi​≤109)，表示每个请求的时间戳。

可以保证所有 n n n 的和不超过 30000 30000 30000。

输出格式

对于每个测试用例，输出 n n n 行，其中第 i i i ( 1 ≤ i ≤ n ) (1≤i≤n) (1≤i≤n) 行包含一个整数，表示 k = i k=i k=i 时不同堆栈的数量。

请注意，答案可能非常大，所以请打印它模 1 0 9 + 7 10^9+7 109+7 代替。

样例

样例输入

2
3
1 2 3
3
2 3 3

样例输出

3
5
5
2
2
2

样例解释

在第一个示例中：

当 k = 1 k=1 k=1 时，栈可以是 [ 1 ] , [ 2 ] , [ 3 ] [1],[2],[3] [1],[2],[3]。
当 k = 2 k=2 k=2 时，栈可以是 [ 1 , 2 ] , [ 1 , 3 ] , [ 2 , 2 ] , [ 2 , 3 ] , [ 3 , 3 ] [1,2],[1,3],[2,2],[2,3],[3,3] [1,2],[1,3],[2,2],[2,3],[3,3]。
当 k = 3 k=3 k=3 时，栈可以是 [ 1 , 2 , 3 ] , [ 1 , 3 , 3 ] , [ 2 , 2 , 3 ] , [ 2 , 3 , 3 ] , [ 3 , 3 , 3 ] [1,2,3],[1,3,3],[2,2,3],[2,3,3],[3,3,3] [1,2,3],[1,3,3],[2,2,3],[2,3,3],[3,3,3]。

在第二个示例中：
当 k = 1 k=1 k=1 时，栈可以是 [ 2 ] , [ 3 ] [2],[3] [2],[3]。
当 k = 2 k=2 k=2 时，栈可以是 [ 2 , 3 ] , [ 3 , 3 ] [2,3],[3,3] [2,3],[3,3]。
当 k = 3 k=3 k=3 时，栈可以是 [ 2 , 3 , 3 ] , [ 3 , 3 , 3 ] [2,3,3],[3,3,3] [2,3,3],[3,3,3]。

题目分析

首先发现我们不关心值的大小，只关心排名，而且貌似需要嗯造到动态规划状态里，所以需要离散化。

我们考虑转换问题，发现类似于填充一个不下降子序列，但是有点限制。

接下来考虑动态规划，我们设 f i , j f_{i,j} fi,j​ 表示填到第 i i i 位，末尾为 j j j。

边界比较清楚， f 1 , j = 1 f_{1,j}=1 f1,j​=1。

我们发现这个填充并不是没有条件的，事实上，我们发现 i ≤ t j ileq t_j i≤tj​， t j t_j tj​ 表示有多少数字小于等于 j j j，因为我们在前面填出的多的 j j j 本质是拿比 j j j 小的数字代替，因此怎么填也填不到 t j t_j tj​ 后面。

我们不难得到转移方程：

f i , j = ∑ k = 1 j f i − 1 , k ( i ≤ t j ) f_{i,j}=sum_{k=1}^jf_{i-1,k}(ileq t_j) fi,j​=k=1∑j​fi−1,k​(i≤tj​)

条件不成立则值为 0 0 0。

不得不说，这个还是比较好想的，但是我们需要优化，加个前缀和即可。

我们用定义一个 s u m sum sum，有：

s u m i , j = ∑ k = 1 j f i , j sum_{i,j}=sum_{k=1}^j f_{i,j} sumi,j​=k=1∑j​fi,j​

以上方程可以写成：

f i , j = s u m i − 1 , j ( i ≤ t j ) f_{i,j}=sum_{i-1,j}(ileq t_j) fi,j​=sumi−1,j​(i≤tj​)

对于第 i i i 个输出：

a n s i = ∑ j = 1 M f i , j ans_i=sum_{j=1}^M f_{i,j} ansi​=j=1∑M​fi,j​

这里的 M M M 表示离散化之后的最大值。

实现代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=3e3+5;
const LL mod=1e9+7;
LL T,n,x[N],a[N],t[N],f[N][N],sum[N][N],cnt,ans[N];
int main()
{scanf("%lld",&T);while(T--){scanf("%lld",&n);memset(t,0,sizeof(t));memset(f,0,sizeof(f));memset(sum,0,sizeof(sum));memset(ans,0,sizeof(ans));for(int i=1;i<=n;i++){scanf("%lld",&x[i]);}sort(x+1,x+n+1);cnt=0;for(int i=1;i<=n;i++){if(x[i]!=x[i-1])cnt++;a[i]=cnt;t[cnt]++;}for(int i=1;i<=cnt;i++)t[i]+=t[i-1];for(int i=1;i<=n;i++){for(int j=1;j<=cnt;j++){if(i==1)f[i][j]=1;else if(i<=t[j])f[i][j]=sum[i-1][j];else f[i][j]=0;ans[i]=(ans[i]+f[i][j])%mod;sum[i][j]=(sum[i][j-1]+f[i][j])%mod;}}for(int i=1;i<=n;i++){printf("%lldn",ans[i]);}}
}

如果你看完了整个文章，下面有投票可以玩，再奖励你看一个科比。