超长序列计数从值域入手（判定转状态）+分析dp状态数量：arc146_e

https://atcoder.jp/contests/arc146/tasks/arc146_e

Trick1 超长序列从值域入手（判定转状态）

通过绝对值的条件，其实我们可以从小到大放每个数。

对于两个相邻的同样数 $i$，他们之间必须放 $i+1$

因此可以设计 $dp[i][j][0/1/2]$ 表示前 $i$ 个数，第 $i$ 个有 $j$ 个相邻的，左右两边有多少个为 $i$

Trick2 分析dp状态数量

此时状态是 $O(n^2)$ 的。

但观察dp的转移过程很单一，相邻之间的转移相差也就1，而且第三维是类似一种层数的东西，只能从高层到低层。

此时大胆猜测状态数并不多。手玩一下可以发现，在第一、三维确定时，第二维的取值只有3种，然后记搜就完事了

int dfs(int i, int o, int k) {
	if(k<0 || k>=a[i]) return 0; 
	if(i<=1) return dp[i][o][k]; 
	if(dp[i][o].find(k)!=dp[i][o].end()) return dp[i][o][k]; 
	int tmp=0; 
	if(o==0) tmp=(dfs(i-1, 0, a[i]-k)+dfs(i-1, 1, a[i]-k)+dfs(i-1, 2, a[i]-k))%mo; 
	if(o==1) tmp=(dfs(i-1, 1, a[i]-k-1)+dfs(i-1, 2, a[i]-k-1)*2)%mo; 
	if(o==2) tmp=dfs(i-1, 2, a[i]-k-2); 
	return dp[i][o][k]=tmp*C(a[i]-1, a[i]-k-1)%mo; 
}
1
2
3
4
5
6
7
8
9
10