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 奇迹

来源： P8227 「Wdoi-5」建立与摧毁的结界

洛谷题解讲的很明白了，不过代码实现上不够清楚

对于 \(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;
}