题解 CF1474F 【1 2 3 4 ...】

· · 题解

看到这个题你会发现它和 [APIO2016]划艇 很像（好吧不是很像但是有点像）。

第一问很好做，因为最长严格上升子序列显然是值域连续的，直接 $n^2$ 枚举起点终点即可。 接下来只要解决第二问，可以发现如果有多种由不同值域构成的最长严格上升子序列，那么每种值域的最长严格上升子序列所在的区间显然是不交的（否则就会更新答案长度），可以分开处理。 先把输入中的 $a_i=0$ 抠掉，再特判只有下降的情况，以方便后面的计算。 接下来是一个类似 APIO 那个题的做法，先将重要的断点（即每个转折点的高度和上下一个高度）存下来离散化。 然后发现值域被断成了若干个区间。 对于每一种值域的答案 dp。设 $f_{i,j}$ 表示第 $i-1$ 到第 $i$ 个断点这段左开右闭的区间，最长严格上升子序列填到第 $j$ 段值域的最高点的方案数。（$f_{1,j}$ 仅表示最前面的一个单点） 每次转移时，枚举上一个填完 $j-1$ 段权值的位置 $k$，然后计算填第 $j$ 段的方案数转移。 可以发现 $k\sim i$ 中包含第 $j$ 段的数大概会长这个样子：`/ \ / \ / \ /`（如果用序列中数的值表示高度的话） 那么上升的段 `/` 可以填任意多个数，下降的段 `\` 只能填一个数。最后填数方案显然只和每段填了多少个数有关。 于是记第 $j$ 段值域长度为 $len$，上升段的个数为 $t1$，记下降段的个数为 $t2$，枚举填数的下降段个数，答案为： $$ \sum_{0\leq i\leq t2} {{t2}\choose{i}}{{len-i+t1-1}\choose{t1-1}} $$ 后面的组合数可以用隔板法推出。 实际计算的时候 $len$ 要 $-1$，因为第 $j$ 段值域最大的数一定要选在序列中第 $i$ 段的位置，否则会算重。 因为后面的组合数中 $len$ 可能很大，但 $t1$ 很小，可以递推求解。 实际实现的时候需要注意一些边界问题。 时间复杂度 $\mathcal O(n^5)$，而且常数非常小，只跑了 31ms，吊打标算。 $\text{Code Below} 
#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=55;
const int p=998244353;

int read()
{
    int s=0;
    char c=getchar(),lc='+';
    while (c<'0'||'9'<c) lc=c,c=getchar();
    while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
    return lc=='-'?-s:s;
}
void write(int x)
{
    if (x<0) putchar('-'),x=-x;
    if (x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
void print(int x,char c='\n')
{
    write(x);
    putchar(c);
}
inline void add(int &x,int y){x+=y;if (x>=p) x-=p;}
int dp[N][N*3],a[N],b[N*3],A[N],ans=0;
int Ca[N][N],inv[N];
int C(int n,int m)
{
    if (n<m||n<0||m<0) return 0;
    if (n<=50) return Ca[n][m];
    int ret=1;
    for (int i=1;i<=m;i++) ret=1LL*ret*(n-i+1)%p*inv[i]%p;
    return ret;
}
int calc(int t1,int t2,int len)
{
    int ret=0;
    for (int i=0;i<=t2;i++)
    ret=(ret+1LL*C(t2,i)*C(len-i+t1-1,t1-1))%p;
    return ret;
}
int solve(int l,int r)
{
    for (int i=l;i<=r;i++) if (a[i]==a[l]) dp[i][a[l]]=1;
    for (int i=l+1;i<=r;i++)
    for (int j=min(A[i-1],a[i]);j<=max(A[i-1],a[i]);j++)
    {
        int t1=0,t2=0,len=b[j+1]-b[j]-1;
        if (a[i-1]<a[i])
        {
            t1=1;
            if (dp[i][j-1]) add(dp[i][j],1LL*dp[i][j-1]*calc(t1,t2,len)%p);
        }
        for (int k=i-1;k>=l;k--)
        {
            if (a[k-1]<a[k])
            if (min(A[k-1],a[k])<=j&&j<=max(A[k-1],a[k])) t1++;
            if (dp[k][j-1]) add(dp[i][j],1LL*dp[k][j-1]*calc(t1,t2,len)%p);
            if (a[k-1]>a[k])
            if (min(A[k-1],a[k])<=j&&j<=max(A[k-1],a[k])) t2++;
        }
    }
    int ret=0;
    for (int i=l;i<=r;i++)
    if (a[i]==a[r]) add(ret,dp[i][a[r]]);
    return ret;
}
inline bool check(int n)
{
    for (int i=1;i<=n;i++) if (a[i-1]<a[i]) return 0;
    return 1;
}

signed main(signed Goodbye,char *Wangang[])
{
    (void)Goodbye,(void)Wangang;
    inv[0]=inv[1]=1;
    for (int i=2;i<=50;i++) inv[i]=1LL*inv[p%i]*(p-p/i)%p;
    for (int i=Ca[0][0]=1;i<=50;i++)
    for (int j=Ca[i][0]=1;j<=i;j++) Ca[i][j]=(Ca[i-1][j-1]+Ca[i-1][j])%p;
    int n=read(),x=read(),Max=0; (void)x;
    for (int i=1;i<=n;i++) a[i]=a[i-1]+read();
    for (int i=0;i<n;i++)
    if (a[i]==a[i+1])
    {
        for (int j=i;j<n;j++) a[j]=a[j+1];
        n--;
        i--;
    }
    for (int i=0;i<=n;i++)
    for (int j=i;j<=n;j++)
    Max=max(Max,a[j]-a[i]+1);
    if (check(n)) return print(Max,' '),print((-a[n]+1)%p),0;
    int cnt=0;
    for (int i=0;i<n;i++)
    if (a[i]<a[i+1]) b[++cnt]=A[i]=a[i]+1;
                else b[++cnt]=A[i]=a[i]-1;
    for (int i=0;i<=n;i++) b[++cnt]=a[i];
    for (int i=1;i<=n;i++) b[++cnt]=a[i]+1;
    sort(b+1,b+cnt+1);
    cnt=unique(b+1,b+cnt+1)-b-1;
    for (int i=0;i<=n;i++) a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
    for (int i=0;i<n;i++) A[i]=lower_bound(b+1,b+1+cnt,A[i])-b;
    for (int i=0;i<=n;i++)
    {
        int r=-1;
        for (int j=i;j<=n;j++)
        if (b[a[j]]-b[a[i]]+1==Max) r=j;
        if (~r) add(ans,solve(i,r)),i=r;
    }
    print(Max,' '),print(ans);

    return 0;
}