Trick 1: 一个关于排列计数的问题

大概是这样一个故事：

AT DP Contest G
一个排列 \(P\)，给你 \(n-1\) 条限制，每个限制表示相邻的两数的大小关系
求排列的方案数
\(n = 3000\)

那么我们有这样一个解法：DP，仅考虑当前相邻两数大小情况。

考虑设 \(f(i,j)\) 表示第 \(i\) 个数，前面比它小的有 \(j\) 个，的方案数。

那么仅考虑与 \(P_{i-1}\) 的关系，以 \(P_{i-1}< P_i\) 为例。

先假设有 \(i\) 个空位，我们把 \(P_i\) 放在了第 \(j+1\) 个空位上，那么比它小的数就有 \(j\) 个。

然后我们把 \(P_{i-1}\) 插在了它的前面某个位子，相当于求 \(\sum \limits_{k<j}f(i-1,k)\)，并且仍然保留“当前共有 \(i-1\) 个空位”这个性质，使得二维 DP 得以实施。

关于枚举 \(k\)：前缀和优化。

void solve(){
	cin>>n;
	cin>>(str+1);
	f[1][0]=1; sum[1][0]=1;
	for(ll i=2;i<=n;i++){
		for(ll j=0;j<i;j++){
			ll lft=j, rht=i-1-j;
			if(str[i-1]=='>'){
				if(!rht) continue;
				f[i][j]=sum[i-1][i-2] - sum[i-1][j-1] + mod;
				f[i][j] %= mod;
			}
			if(str[i-1]=='<'){
				if(!lft) continue;
				f[i][j]=sum[i-1][j-1];
			}
		}
		sum[i][0]=f[i][0];
		for(ll j=1;j<i;j++) sum[i][j]=(sum[i][j-1]+f[i][j])%mod; 
	}
	ll ans=0;
	for(ll i=0;i<n;i++) ans=(ans+f[n][i])%mod;
	cout<<ans<<endl;
}

AT abc282 g
两个排列 \(A,B\)
求有多少种有序排列对 \((A,B)\) 满足：
恰好有 \(k\) 个 \(i\) 满足 \((A_{i+1}-A_i)(B_{i+1}-B_i)>0\).

我第一眼想到的是按 \(A_i\) 的顺序插入，但是 \(B_i\) 无需不好维护。想想上面的题对这题有无帮助。

若考虑按顺序 DP，维护 \(A\) 的插入情况和 \(B\) 的插入情况，要好做的多。

\(f(i,j,k,l)\) 表示第 \(i\) 个位置，\(A\) 排列中当前元素前面有 \(j\) 个数，\(B\) 有 \(k\) 个数，一共是 \(l\) 个相同的大于小于情况。转移的话需要二维前缀和优化 /tuu 超级恶心吧

虽然 1024MB 的空间，可能还是要滚一下。暂时没写代码。

Luogu P4099