还是之前做的题。。还是一样的毫无印象。。。我是SB
给的(x)是没有用的。
最长上升子序列的长度可以直接枚举起点终点(O(n^2))求解。困难的是计数部分。
找出序列中所有的极长段使得开头至结尾能形成最长上升子序列。
（就是每一段开头结尾最小值和最大值都在减小）
对于每一个极长段分别求解。
暴力DP就是(dp_{v,i})表示当前值(v)，当前所在段为(i)的方案数。
优化再一次用到了apio划艇和noi机器人的把值域分段的技巧。。然而我还是没掌握
就是升序枚举值域段，有一些段合法且转移相同，用矩阵快速幂优化。
这个做法还得把(0)全都删掉还有特判全是负数的情况。。
时间复杂度(O(n^4log A))
感觉自己还是说不明白。。看代码吧，我真的太菜了
#include <bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define mem(a) memset((a),0,sizeof (a))
#define O(x) cerr<<#x<<':'<<x<<endl
#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=52,mod=998244353;
inline void tmod(int &x){x%=mod;}
int n,tot,a[MAXN],ans,sum,res,m,L[MAXN],R[MAXN],sta[MAXN*2],top;
struct mat{
int a[MAXN][MAXN];
inline mat operator*(const mat &b)const{
mat c;fp(i,0,m)fp(j,0,m)c.a[i][j]=0;
fp(k,0,m)fp(i,0,m)fp(j,0,m)tmod(c.a[i][j]+=a[i][k]*b.a[k][j]);
return c;
}
};
inline mat qpow(mat a,int b){
mat c;fp(i,0,m)fp(j,0,m)c.a[i][j]=0;
fp(i,0,m)c.a[i][i]=1;
for(;b;b>>=1,a=a*a)
if(b&1)c=c*a;
return c;
}
inline int calc(int l,int r){
m=r-l+1;tot=0;int s=0;
fp(i,l,r){
++tot;
L[tot]=(s+(a[i]<0?-1:1));R[tot]=s+a[i];
s+=a[i];
}
top=0;L[1]=0;
fp(i,1,m){
sta[++top]=min(L[i],R[i]);sta[++top]=max(L[i],R[i])+1;
}
sort(sta+1,sta+1+top);top=unique(sta+1,sta+1+top)-sta-1;
mat ans,tmp;
fp(i,0,m)fp(j,0,m)ans.a[i][j]=0;ans.a[0][0]=1;
fp(kk,1,top-1){
int l=sta[kk],r=sta[kk+1]-1;
fp(i,0,m)fp(j,0,m)tmp.a[i][j]=0;
fp(i,1,m)if(min(L[i],R[i])<=l&&max(L[i],R[i])>=r){
if(L[i]<R[i])fp(j,0,i)tmp.a[j][i]=1;
else fp(j,0,i-1)tmp.a[j][i]=1;
}
ans=ans*qpow(tmp,r-l+1);
}
int ss=0;
fp(i,0,m)tmod(ss+=ans.a[0][i]);
return ss;
}
main(){
n=read();read();
fp(i,1,n){
int t=read();
if(t)a[++tot]=t;
}
n=tot;
fp(i,1,n){
int t=sum;
fp(j,i,n){
t+=a[j];
ans=max(ans,t-sum);
}
sum+=a[i];
}
if(!ans){
int t=1;
fp(i,1,n)tmod(t-=a[i]);
printf("1 %lld
",t);
return 0;
}
fp(i,1,n){
int t=0,p=0;
fp(j,i,n){
t+=a[j];
if(t==ans){
p=j;//you can't break here!
}
}
if(p)tmod(res+=calc(i,p)),i=p;
}
printf("%lld %lld
",ans+1,res);
return 0;
}