T1 y
什么寄吧。
懂了，不会的题就先排个序。
T2 s
这个题打了一个 dfs 求 10 以内全排列跑路了。
对于题里给的这个函数，\(1-n\) 的全排列求和：
int f(int n,int p[],int s[]){
int ret=p[1];
for(int i=2;i<=n;i++){
if(s[i-1]==1)ret=max(ret,p[i]);
else ret=min(ret,p[i]);
}
return ret;
}
求 \(\sum_{ret\ge 1}\limits ret\) 可以转换为：
\[ \begin{aligned} ret=\sum_{i=1}^{n}\limits [ret\ge i] \end{aligned} \]（注：\([ret\ge i]\) 返回值是 bool 类型，即贡献为 \(1\)）
那么可以考虑对每一个 \(i\) 计算 \(\sum_{p}\limits [ret\ge i]\)，即求 \(p\) 的全排列下 \(ret\ge i\) 的个数。
现在我们只需要知道 \(ret\) 是否 \(\ge i\)，所以不用关系 \(p\) 是什么样子，而是关系他们与 \(i\) 的大小关系：
把 \(\ge i\) 的数看做 \(1\)，把 \(<i\) 的数看做 \(0\)，如果最后 \(ret==1\) 那么肯定是取到了 \(>1\) 的结果，计算 \(ret==1\) 的方案数。
于是我们从 \(i=n\) 枚举到 \(i=1\)，将问题转化为：
在长度为 \(n\) 的序列，填入 \(i\) 个 \(1\)，使得 \(ret==1\) 的方案数。
设计动态规划：
设 \(f_{i,j,k}\) 表示当前填了第 \(i\) 个数，已经填了 \(j\) 个 \(1\)（包括第 \(i\) 位），当前 \(ret\) 为 \(0/1(k)\) 的方案数。
有转移：
-
当前 \(ret\) 是 \(1\)，由第 \(i-1\) 位置的：\((1,1),max(1,0),max(0,1)\) 转移。
-
当前 \(ret\) 是 \(0\)，由第 \(i-1\) 位置的：\((0,0),min(0,1),min(1,0)\) 转移。
即：
\[ \begin{aligned} &f_{i,j,1}=f_{i-1,j-1,1}+(s_{i-1}==1)(f_{i-1,j,1}+f_{i-1,j-1,0})\\ &f_{i,j,0}=f_{i-1,j,0}+(s_{i-1}==0)(f_{i-1,j-1,0}+f_{i-1,j,1}) \end{aligned} \]答案从 \(f_{n,i,1}\) 中寻找。从 \(i=2,j=0\) 开始枚举，特别地 \(i==1\) 时 \(f_{1,1,1}=1\)，\(f_{1,0,0}=1\)。
由于我们是填的 \(01\) 的方案，实际上数是不重复的即各不相同的，所以要乘上 \(i!(n-i)!\) 才是实际序列方案数。
（即 \(1\) 的排列 \(A_i^i\) 与 \(0\) 的排列 \(A_{n-i}^{n-i}\) 的乘积）
最后因为当前状态只与上一状态有关（且恶心的 256MiB 内存限制），所以使用滚动数组。
Miku's Code
#include<bits/stdc++.h>
using namespace std;
typedef long double llf;
typedef long long intx;
const int maxn=5e3+50,mod=998244353;
int n,s[maxn];
int cur;
intx fac[maxn];
intx f[2][maxn][2];
void pre(){
//预处理阶乘
fac[0]=1;fac[1]=1;
for(int i=2;i<=maxn-1;++i){
fac[i]=fac[i-1]*i%mod;
}
}
void input(){
scanf("%d",&n);
for(int i=1;i<=n-1;++i){
scanf("%d",&s[i]);
}
}
void work(){
for(int i=2;i<=n;++i){
cur=cur^1;
for(int j=0;j<=n;++j){
if(j==0){
f[cur][j][1]=(s[i-1]==1)*(f[cur^1][j][1])%mod;
f[cur][j][0]=f[cur^1][j][0]+(s[i-1]==0)*f[cur^1][j][1]%mod;
}
else{
f[cur][j][1]=(f[cur^1][j-1][1]+(s[i-1]==1)*(f[cur^1][j][1]+f[cur^1][j-1][0])%mod)%mod;
f[cur][j][0]=(f[cur^1][j][0]+(s[i-1]==0)*(f[cur^1][j-1][0]+f[cur^1][j][1])%mod)%mod;
}
}
}
}
signed main(){
pre();
input();
f[cur][1][1]=1;
f[cur][0][0]=1;
work();
intx ans=0;
for(int i=1;i<=n;++i){
ans=(ans+f[cur][i][1]*fac[i]%mod*fac[n-i]%mod)%mod;
}
printf("%lld",ans);
return 0;
}