题目背景
“能上得了这所学校的孩子真的是超级超级幸运！在西安众多的民办小学中，这所学校绝对是佼佼者！有十分优秀的教师团队，还有超级有魄力有眼光的校长。校园整体环境古朴典雅，园林式的环境，硬件设施也是相当完善，各种场馆都有配置，图书馆还能针对本学校学生免费借阅，游泳馆今年也全面开放，给孩子们上学提供了很多便利，让孩子们可以提高综合素质；学校办学很有特色，各种活动也丰富多样，注重培养孩子全方面发展，学校英语数学和语文唐诗都有自己独特的教材，老师管理也很好，能及时发现孩子的问题及时和家长沟通，做到家校共建，孩子在学校期间包含午餐午点和晚餐，整体后勤保障工作做得全面，教学理念很好，把孩子放在这样强大的学校里家长们特别放心！”
看完了这则超正面的反馈，校长的脸色却不怎么好。
“夸新知小学，怎么能忘了我们的神———LJH呢！”
题目描述
敬业的校长每天都会看$n$条来自社会各界对新知小学办学的反馈。然而，他看反馈只关注里面有没有出现新知之神LJH，如果有，他就会很满意；反之如果没有，他就会很郁闷。但是如果他先看了几条没有出现新知之神LJH的反馈，再看到一系列有的，就会感到加倍的欣慰。具体而言，如果用一个长度为 $n$ 的 01 序列来表示反馈的话，0 表示反馈中没有出现新知之神 LJH，1 表示反馈中出现了新知之神 LJH，那么校长的快乐程度就是这个 01 序列中的最长不降子序列长度。
LJH作为新知之神，掌握一些魔法。他非常感激校长对他的厚爱，于是也同样希望校长可以笑一笑十年少。LJH可以对一段连续的区间进行一次取反操作（即 0 变 1， 1 变 0）。
注意，LJH进行操作的区间必须有正长度。
你作为新知之神LJH的小粉丝，需要替他计算操作完之后校长的最大快乐程度，以及能够导出这个最大快乐程度的不同方案数。
两个方案是不同的，当且仅当LJH操作的区间不同，或者在操作后导出最大快乐程度的最长不降子序列不同。
方案数对 $10^9+7$ 取模。
输入格式
第一行一个数 $T$，表示数据组数。
对于每组数据：
- 第一行一个数 $n$， 表示序列长度。
- 第二行一个长度为 $n$ 的 01 字符串。
输出格式
$T$ 行，每行两个数，分别表示最大快乐程度和方案数，两个数之间用一个空格分隔。
方案数对 $10^9+7$ 取模。
样例输入 1
3
1
0
4
1001
2
11样例输出 1
1 1
4 3
2 2样例解释
第二组样例的 3 种方案：
- 取反区间 $[1,1]$，得到
0001 - 取反区间 $[1,3]$，得到
0111 - 取反区间 $[2,3]$，得到
1111
样例输入 2
2
5
01010
5
01000样例输出 2
4 12
5 3数据范围
对于 $20\%$ 的数据，$n\le 100$。
对于 $40\%$ 的数据，$n\le 500$。
对于 $60\%$ 的数据，$n\le 3000$。
对于 $80\%$ 的数据，$n\le 10^4$。
对于 $100\%$ 的数据，$T\le 10, n \le 10^5$。
时间限制：1000ms
空间限制：512MB
对于一个点，他与反转区间的关系有三种：在前面，在中间，在后面。
定义 \(dp_{i,j,k}\) 为前 \(i\) 个数，最长不降子序列的结尾是 \(j\) ，与区间的关系是 \(k\) 的最长序列和方案数。
那么枚举上一位的各种情况和这一位是否取，dp就可以了
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,P=1e9+7;
int t,n,dp[N][2][3],a[N],ans,ret;//dp[i][j][k],j表示上一位，k(0/1/2)表示第i位在区间左/中/右，
long long f[N][2][3];
char c;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
memset(dp,ans=ret=0,sizeof(dp));
memset(f,0,sizeof(f));
f[0][0][0]=1;
for(int i=1;i<=n;i++)
{
scanf(" %c",&c);
a[i]=c-'0';
for(int j=0;j<=1;j++)
{
for(int k=0;k<=2;k++)
{
int t=a[i]^(k==1);
dp[i][j][k]=dp[i-1][j][k];
if(k)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]);
if(t==j)
{
for(int l=0;l<=j;l++)
{
dp[i][j][k]=max(dp[i][j][k],dp[i-1][l][k]+1);
if(k)
dp[i][j][k]=max(dp[i][j][k],dp[i-1][l][k-1]+1);
}
for(int l=0;l<=j;l++)
{
if(dp[i][j][k]==dp[i-1][l][k]+1)
f[i][j][k]+=f[i-1][l][k];
if(k&&dp[i][j][k]==dp[i-1][l][k-1]+1)
f[i][j][k]+=f[i-1][l][k-1];
f[i][j][k]%=P;
}
}
if(dp[i][j][k]==dp[i-1][j][k])
f[i][j][k]+=f[i-1][j][k],f[i][j][k]%=P;
if(k&&dp[i][j][k]==dp[i-1][j][k-1])
f[i][j][k]+=f[i-1][j][k-1],f[i][j][k]%=P;;
}
}
}
for(int i=0;i<2;i++)
for(int j=1;j<3;j++)
ans=max(ans,dp[n][i][j]);
for(int i=0;i<2;i++)
for(int j=1;j<3;j++)
if(dp[n][i][j]==ans)
ret+=f[n][i][j],ret%=P;
printf("%d %d\n",ans,ret);
}
}