我计数咋这么菜。

题目链接

P7213 - [JOISC 2020] 最古の遺跡 3

解题思路 & 参考代码

贡献延后转移 trick。

首先我们容易注意到对于一个合法的初始石柱状态，最终一定只会剩下

1 \sim n

中的数，且每个数恰好出现一次。

具体证明就是，初始

1 \sim n

所有数出现

2

次，显然的，对于一个数

x

若出现了两次，则一次操作会将其中一个

x

变为

x-1

，若

x-1

也有两个数，则其中一个

x-1

会变为

x-2

，因此，一次操作后，所有的数字出现个数仍然

\le 2

，该结论成立。

考虑刻画这个形式，容易发现为遍历

i = n,n-1,\dots,2,1

，把最后一个

\ge i

且之前未被标记过的数标记，最终被标记的位置就为原序列的最终石柱位置。

但是这东西不好直接做，考虑直接对着原序列

a

进行刻画，可以发现我们可以直接遍历

i = 2n,2n-1,\dots,2,1

，同时在遍历过程中维护一个集合

S

，如果此时

S

中包含了

1,2,3,\dots,a_i

，那么

i

不能被加入

S

内，否则我们可以往

S

内加入一个最大的

\le a_i

的不在

S

中的数，设其为

a_i'

（若没有则

a_i' = 0

），此时

i

为其中一个最终石柱位置。

容易注意到这两个东西事实上是等价的，所以这样是对的。

刻画完后，我们可以考虑 dp。

为了方便，我们在下文转移时钦定所有数均是不同的，最后将答案乘上

\displaystyle\frac{1}{2^n}

即可。

假设从后往前第

i

个位置之前（不含第

i

个位置）已经有

s_0

个位置不为最终石柱位置，

s_1

个位置为最终石柱位置。

设

f_{i,j}

表示考虑了后

i \sim 2n

个数，

S

中含有

1 \sim j

且不含有

j+1

的方案数，考虑如何转移

f_{i,j}

：

如果我们钦定第 $i$ 个位置不为最终石柱位置，那么权值可以从 $1 \sim j$ 中选取，由于之前最终石柱位置选取了 $j$ 个，不在最终石柱位置的位置有 $s_0$ 个，那么方案数就为 $(j - s_0)$ ，有转移： $(j-s_0)f_{i+1,j} \to f_{i,j}$
如果我们钦定第 $i$ $i$ 个位置为最终石柱位置，可以进行以下分讨：
- 若 $a_i \ge a_i' > j + 1$ ，考虑延后转移，即： $f_{i+1,j} \to f_{i,j}$
- 否则有 $a_i' = j + 1$ $a_{i}^{'} = j + 1$ ，那么此时 $j$ $j$ 会改变，枚举 $j$ $j$ 变为了 $k \in [j+1,s_1+1]$ $k \in [j + 1, s_{1} + 1]$ ，那么我们需要把延迟转移的 $a'$ $a^{'}$ 拿来填 $[j+2,k]$ $[j + 2, k]$ ：
  - 显而易见的，决定延迟转移的柱子数量为 $(s_1 - j)$ ，选其中的 $k - (j + 2) + 1 = k-j-1$ ，为 $\displaystyle\binom{s_1 - j}{k-j-1}$ 。
  - 然后我们需要考虑 $a_i$ 必须要满足 $a_i' = j + 1 \le a_i \le k$ ，有 $(k - j + 1)$ 种方案。
  - 这里我们需要设一个 $g_x$ 表示有 $x$ 根柱子，操作后高度 $a'$ 连续的方案数，因此我们需要带一个 $g_{k-j-1}$ 的系数，有转移： $f_{i+1,j}\displaystyle\binom{s_1 - j}{k-j-1}(k - j + 1)g_{k-j-1} \to f_{i,k}$

考虑如何转移

g_x

，可以枚举第一根柱子的最终高度

i

，然后之后的

x-1

根柱子需要选取

i-1

个位置，方案数即为

\displaystyle\binom{x-1}{i-1}

，同时容易注意到

<i

与

>i

的部分是相互独立的，所以可以直接乘上

f_{i-1}f_{x-i}

，考虑

a_1

的方案数，

i \le a_1

初始有

2(x-i-1)

种，由于有

x-i

种已经被选过了，因此还剩下

(x - i + 2)

种，因此有转移：

g_x = \displaystyle\sum_{i=1}^{x} \binom{x-1}{i-1} g_{i-1} g_{x-i} (x-i+2)

。

于是就做完了，时间复杂度

O(n^3)

。

参考代码

CPP

ll n,m;
ll vis[1210],f[1210][1210],g[1210];
ll s0,s1;
void solve()
{
	cin>>n;
	forl(i,1,n)
		vis[rd()]=1;
	m=n*2;
	g[0]=1;
	forl(x,1,m)
		forl(i,1,m)
			add(g[x],g[i-1]*g[x-i]%mod*C(x-1,i-1)%mod*(x-i+2)%mod);
	f[m+1][0]=1;
	forr(i,m,1)
	{
		if(vis[i])
		{
			forl(j,0,s1)
			{
				add(f[i][j],f[i+1][j]);
				forl(k,j+1,s1+1)
					add(f[i][k],f[i+1][j]*C(s1-j,k-j-1)%mod*(k-j+1)%mod*g[k-j-1]%mod);
			}
			s1++;
		}
		else
		{
			forl(j,s0,n)
				add(f[i][j],(j-s0)*f[i+1][j]%mod);
			s0++;
		}
	}
	cout<<pw(pw(2,n,mod),mod-2,mod)*f[1][n]%mod<<endl;
}

题解：P7213 [JOISC 2020] 最古の遺跡 3

文章操作

题目链接

解题思路 & 参考代码

相关推荐

评论

题解：P7213 [JOISC 2020] 最古の遺跡 3