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约减,并且对加法不取模,就过了。
code
Submission #230099002 - Codeforces
标签:10,可以,自然数,权值,长度,CF1553I,条链 From: https://www.cnblogs.com/FreshOrange/p/17793757.html