T1 平凡
首先，我们容易发现直接求 \(A\) 不是最小的子序列的排列的个数有些困难
#include<bits/stdc++.h>
#define mod 998244353
#define N 1000010
#define int long long
using namespace std;
int n,k,a[N],t[N],vis[N],ans,all,pos;
signed main(){
freopen("ordinary.in","r",stdin);
freopen("ordinary.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
ans = all = 1;
for(int i = k+1;i<=n;i++)
all = all*i%mod;
for(int i = 1;i<=k;i++){
cin>>a[i];
t[a[i]] = 1;
}
for(int i = 1;i<=k;i++){
if(a[i]>a[i+1]){
pos = i;
for(int j = i+1;j<=k;j++)
vis[a[j]] = 1;
break;
}
}
int sum = 0;
for(int i = 1;i<=n;i++){
if(!vis[i]){
if(!t[i])
ans = ans*(sum+(i>a[pos]))%mod;
sum++;
}
}
cout<<(all-ans+mod)%mod;
return 0;
}
T2 奇迹
洛谷题解讲的很明白了，不过代码实现上不够清楚
对于 \(pre\) 函数就是处理出了每一个括号配对的位置
\(getans\) 函数就是就是题解中所说的 \(f,g\) 两个数组，对于 \(flag\) 就是判断到底当前是哪种序列
\(dfs\) 函数就是对于每一个区间递归计算答案，先处理出哪些左括号是当前层的左括号
然后比较两个字符串是否相同，当前层相同则不操作，否则计算答案，最后还原数组
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n,ans,apair[N],bpair[N],aleft[N],bleft[N];
char a[N],b[N];
inline void pre(char s[],int t[]){
stack<int>stk;
for(int i = 1;i<=n;i++){
if(s[i]==')'){
t[i] = stk.top();
t[t[i]] = i;
stk.pop();
}else stk.push(i);
}
}
int getans(int t[],int l,int r,bool flag){
if(l+1==r) return 0;
if(t[l+1]==r-1){
if(!flag) return getans(t,l+1,r-1,1)+1;
return getans(t,l+1,r-1,1);
}else{
int res = 0;
for(int i = l+1;i<r;i = t[i]+1)
res+=getans(t,i,t[i],0);
return res+(flag?1:2);
}
}
int dfs(int l,int r){
if(l+1==r) return 0;
int res = 0;
for(int i = l;i<=r;i = apair[i]+1) aleft[i] = 1;
for(int i = l;i<=r;i = bpair[i]+1) bleft[i] = 1;
for(int i = l;i<=r;i = apair[i]+1)
if(bleft[i]&&apair[i]==bpair[i])
res+=dfs(i+1,apair[i]-1);
for(int i = l;i<=r;i = apair[i]+1)
if(!bleft[i]||apair[i]!=bpair[i])
res+=getans(apair,i,apair[i],0);
for(int i = l;i<=r;i = bpair[i]+1)
if(!aleft[i]||apair[i]!=bpair[i])
res+=getans(bpair,i,bpair[i],0);
for(int i = l;i<=r;i = apair[i]+1) aleft[i] = 0;
for(int i = l;i<=r;i = bpair[i]+1) bleft[i] = 0;
return res;
}
int main(){
freopen("miracle.in","r",stdin);
freopen("miracle.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>a+1>>b+1;
pre(a,apair);
pre(b,bpair);
cout<<dfs(1,n);
return 0;
}