白川京
takanashi_mifuru · · 题解
做法千奇百怪，来分享一下我的做法。
有一个非常不牛的想法就是，直接计算操作序列的种类数，显然是错的。
容易发现矛盾点在于两个点
然后又有一个非常不牛的想法就是，如果对于两个相同的点，而他们的后面不相同，则他们的结果集合完全不交，反之一定相同，我们打个表发现他是错的。
但是这启发我们，两个序列如果要相同他的条件十分苛刻，不仅要锁他自己，还得锁后面的步骤一直到整个序列结束。
于是考虑将连续的删除步骤合并在一起，会是一个交错的形式直到两个序列全部删空，容易想到把他扔到表格里。
那么现在就是一个
考虑我们要刻画一条路径与其他路径本质不同，有很多种办法，比如说我们可以检查一条路径是不是最左上的，如果是才计数。
譬如这张图，点处表示这个地方往上和往右是一样的颜色，考虑两条红色的路径是没有区别的。
所以有一个非常弱智的想法就是我只检查正方形，每次用正方形翻折一条路径，显然是错误的。
如图所示，他也可以是这样的搞笑情况。
我们观察这个情况，尝试在里面寻求可以用来 dp 的状态，容易发现有两点：
- 端点相交
- 所有相等点都在对角线上
- 在右下部分（为防止算重）
然后你就可以记录三维状态分别表示坐标与当前段的对角线的位置，每次走一步就检查当前颜色的相同点是否仍然在这条对角线上，如果不在则这一段失效，否则就继续，直到下一次我当前坐标踩在相同点上的时候我检查是否这一段全部有效，如果有效说明非法那就不转移，反之直接转移。
这样的话是三次方的，你考虑如何优化转移方程。
容易发现你到达点
时间复杂度
丑陋的代码，其中左转移和下转移的实现方法不同没什么深意，主要是修改的时候改了一半发现根本不需要改转移可以直接优化状态数量，然后就懒得搞了。
#include<bits/stdc++.h>
using namespace std;
int A[1005];
int B[1005];
int dp[2][1005][4005][2];
const int delta=2000;
int n;
pair<int,int> need[1005];
int slo[1005];
const int P=1e9+7;
vector<int> val[1005][1005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
for(int i=1;i<=n;i++)scanf("%d",&B[i]);
for(int i=1;i<=n;i++)need[A[i]].first=i,need[B[i]].second=i;
for(int i=1;i<=n;i++)slo[i]=need[i].first-need[i].second+delta;
dp[1][1][delta][1]=1;
val[1][1].push_back(delta);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==1&&j==1)continue;
val[i][j].push_back(slo[A[i]]);
val[i][j].push_back(slo[B[j]]);
sort(val[i][j].begin(),val[i][j].end());
if(val[i][j][0]==val[i][j][1])val[i][j].pop_back();
}
}
for(int i=1;i<=n;i++){
int now=i&1;
int pre=!now;
if(i>2){
for(int j=1;j<=n;j++){
for(int k:val[i-2][j]){
dp[now][j][k][0]=dp[now][j][k][1]=0;
}
}
// memset(dp[now],0,sizeof(dp[now]));
}
for(int j=1;j<=n;j++){
if(i==1&&j==1)continue;
if(i>1){
int col=B[j];//
if(need[col].first==i&&need[col].second==j){
for(int k:val[i-1][j]){
for(int k1=0;k1<2;k1++){
int nxt=slo[col];
if(slo[col]==k&&(i-j+delta<=k)&&k1){
continue;
}
dp[now][j][nxt][1]+=dp[pre][j][k][k1];
if(dp[now][j][nxt][1]>=P)dp[now][j][nxt][1]-=P;
}
}
}
else{
for(int k:val[i-1][j]){
bool flg=true;
if(slo[col] xor k)flg=false;
if(i-j+delta>k)flg=false;
for(int k1=0;k1<2;k1++){
int n1=k1,nxt=slo[col];
n1&=flg;
dp[now][j][nxt][n1]+=dp[pre][j][k][k1];
if(dp[now][j][nxt][n1]>=P)dp[now][j][nxt][n1]-=P;
}
}
}
}
if(j>1){
int col=A[i];
for(int k:val[i][j-1]){
for(int k1=0;k1<2;k1++){
if(dp[now][j-1][k][k1]){
int n1=k1,nxt=slo[col];
if(slo[col] xor k)n1=0;
if(n1&&(i-j+delta>k))n1=0;
bool flg=true;
if(need[col].first==i&&need[col].second==j){//
if(n1)flg=false;
nxt=slo[col];
n1=1;
}
if(flg){
dp[now][j][nxt][n1]+=dp[now][j-1][k][k1];
if(dp[now][j][nxt][n1]>=P)dp[now][j][nxt][n1]-=P;
}
}
}
}
}
}
}//
int ans=0;
for(int k=delta-n;k<=delta+n;k++){
ans+=dp[n&1][n][k][0];
if(ans>=P)ans-=P;
ans+=dp[n&1][n][k][1];
if(ans>=P)ans-=P;
}
printf("%d\n",ans);
return 0;
}//