description
对于一个 \(1\) 到 \(n\) 的排列 \(p\)，第 \(i\) 个位置的权值是 \(p\) 中数字 \(i\)，所在的连续自然数段的长度（可以递增，也可以递减）。现在给定一个数组 \(a\)，求第 \(i\) 个位置权值为 \(a_i\) 的排列 \(p\) 的个数。
\(n\leq 10^5\)
10.0 s 1024 MiB
solution
数组 \(a\) 中相邻的位置权值相同则可以合成一段长度为权值的链，它们在排列中一定是连续的。例如 \([2,2,2,2,3,3,3,1,1,1]\)，我们拆成 \([1,2],[3,4],[5,6,7],[8,8],[9,9],[10,10]\) 几段。显然如果不能恰好拆出这些数链，答案为 0，判掉即可。
现在就是知道有 \(m\) 条数链，每条可以正着也可以反着（长度为 1 的需要特殊处理）。不能有两条链接在一起形成更长的连续自然数段。设 \(g_{i}\) 表示这 \(m\) 条链中钦定有 \(i\) 个链的连接处左右两侧的链可以拼成更长的自然数段，二项式反演得，答案为 \(\sum\limits_{i=0}^m(-1)^i g_{i}\)。下面考虑如何求 \(g_i\)。
设 \(f_{i,j}\) 表示前 \(i\) 条链中钦定 \(j\) 个链的连接处左右两侧的链可以拼成更长的自然数段的方案数，则 \(g_i=f_{m,i}\)。如果不存在长度为 1 的链，转移是好做的：
-
\(f_{0,0}=1\)
-
\(f_{i,j}=2(i-j)\times f_{i-1,j}+f_{i-1,j-1}\)
但是长度为 1 的链会带来较多的麻烦，尝试尝试可以发现这个状态是不好转移的。我们给状态增加一维 01，\(f_{i,j,0/1}\) 表示前 \(i\) 条链中钦定 \(j\) 个链的连接处左右两侧的链可以拼成更长的自然数段，且第 \(i\) 条链是否和前面的链拼接起来的方案数。
这样只要讨论当前链长度是否为 1，以及上一个链长度是否为 1，总共四种情况。可以得出如下代码：（\(n\) 是上文所说的 \(m\)，\(b_i\) 表示第 \(i\) 条链的长度，dp 使用了滚动数组）
...
f[0][0][0]=1;
for(int i=1; i<=n; i++){
int x=i&1;
if(b[i]==1){
for(int j=0; j<i; j++){
f[x][j][0]=(f[x^1][j][0]+f[x^1][j][1])*(i-j)%mod;
if(j){
if(b[i-1]==1){
f[x][j][1]=(f[x^1][j-1][0]*2+f[x^1][j-1][1])%mod;
}
else{
f[x][j][1]=(f[x^1][j-1][1]+f[x^1][j-1][0])%mod;
}
}
}
continue;
}
for(int j=0; j<i; j++){
f[x][j][0]=(f[x^1][j][0]+f[x^1][j][1])*(i-j)*2%mod;
if(j){
if(b[i-1]==1){
f[x][j][1]=f[x^1][j-1][1]+f[x^1][j-1][0]*2;
f[x][j][1]%=mod;
}
else{
f[x][j][1]=(f[x^1][j-1][1]+f[x^1][j-1][0])%mod;
}
}
}
}
...
这份代码时间复杂度 \(O(n^2)\)，常数特别大，过不去，考虑常数优化。
取模极慢，改成 barret约减，并且对加法不取模，就过了。