CF1776N Count Permutations 题解
littlez_meow
·
·
题解
好神的 3500 题！！！
参考论文：第一篇、第二篇。
题目指路。
step 1：转化题意
看到这个大于号和小于号的字符串，完全没有头绪。
有没有什么和它很像的东西？括号序列？
括号序列常用的转化有把左右括号看成向右和向上走，这里的大于小于号可不可以也看成这样呢？
对于一个大于号，我们向右走；对于一个小于号，我们往上走。这样，可以走出来一个长度为 n 的网格路径。
这时，我们往走出来的路径里填数，使之满足给定的不等关系，网格路径里的数就会从左往右严格递减、从上往下严格递减，且恰好不重不漏填入 1-n。
这是什么？斜标准杨表！
step 2：斜标准杨表计数
尝试使用斜标准杨表的钩长公式 Naruse 公式：
|\operatorname{SSYT}(\lambda / \mu)|=|\lambda / \mu| ! \sum\limits_{D \in \mathcal{E}(\lambda / \mu)} \prod\limits_{u \in\lambda / D} \dfrac{1}{\operatorname{hook}(u)}
其中 \mathcal{E}(\lambda / \mu) 为兴奋图的集合，定义详见论文。
这样计算，由于要枚举兴奋图，是指数级的复杂度，还不如直接枚举。
有什么性质是我们没用到的？
再看我们的斜标准样表，它的宽度始终为 1，也就是为一个杨表的边界！
这样，构建兴奋图时的兴奋的移动，就只能在边界上进行替换。而这样的替换，会使每次的间隔始终为一条从左下角到右上角的仅向右或向上的路径，即 \lambda / D 为一条路径。
因此，兴奋图什么的根本就可以不要，我们只要枚举从左下角到右上角的路径 P 就可以计算答案。得到上式在本题的推论，答案为：
|\lambda / \mu| ! \sum\limits_P\prod\limits_{u \in P} \dfrac{1}{\operatorname{hook}(u)}
## step 3：动态规划
这个部分就比较显然了，设 $dp(i,j)$ 表示当前往右走了 $i$ 格，往上走了 $j$ 格的 $\sum\limits_P\prod\limits_{u \in P} \dfrac{1}{\operatorname{hook}(u)}$ 的值。
其中 $P$ 为从左下角到 $(i,j)$ 仅向右或向上的路径。
$P$ 有两种情况，从左边和从下面转移，对于每个路径，里面的求积号都要乘上 $\operatorname{hook}(i,j)$，可以用乘法分配律提到求和号前面，得到状态转移方程：
$$dp(i,j)=(dp(i-1,j)+dp(i,j-1))\times\dfrac 1{\operatorname{hook}(i,j)}$$
用滚动数组可以把空间复杂度优化到 $O(n)$。
直接 dp 时间复杂度是 $O(n^2)$ 的，仍然过不了本题，怎么办？
## step 4：精度
看到这节的标题，你可能会比较疑惑：优化时间复杂度和精度有什么关系呢？
请先思考，为什么题目要求对数而不是取模？
回过头去看看答案的计算式，其中有一个钩长的倒数求积。如果钩长都很大，那这个积就会很小，对求和基本上没有影响，再加上取对数就更不会有什么贡献了。
因此，我们可以舍弃掉对答案贡献极小的点，即钩长较长的点。而一个点的钩长长，代表它和右下边界的切比雪夫距离长。
我们设定一个阈值 $d$，只计算到边界切比雪夫距离小于等于 $d$ 的点，这样就减少了很多计算量，时间复杂度降低到 $O(dn)$，视 $d$ 为常数就是 $O(n)$，可以通过。
在本题 $d$ 取 $500$ 即可。
最后还要解决求以 $2$ 的对数的问题。我们当然可以直接在 $dp$ 时就存对数值，本来要相乘的相加，本来要相加的用下式计算：
$$\log_2(x+y)=\log_2(y)+\log_2(1-2^{\log_2(x)-\log_2(y)})$$
其中 $x<y$。
但是，其中要求幂函数和对数函数，常数奇大无比，你连[第五个点都过不去](https://www.luogu.com.cn/record/126511314)。
换一种方式，由于求对数可以把指数放下来，我们考虑手动模拟科学计数法，速度会快很多。
最后，不要忘记要乘上 $n!$，即加上 $\sum\limits_{i=1}^n \log_2(i)$。
至此，本题解决。
## step 5：附上代码
给出核心 dp 部分代码，$h,w$ 表示杨表的长和宽，$c$ 和 $r$ 记录边界：
```cpp
int posx(w),posy(h);
memset(c,0x7f,sizeof(c));
c[posx]=posy,r[posy]=posx;
R(i,n-2,0){
char ch=S[i];
ch=='>'&&(--posx);
ch=='<'&&(--posy);
c[posx]=min(c[posx],posy),r[posy]=max(r[posy],posx);
}
dp[0][1].val=1;
F(i,1,w){
int now(i&1),last(now^1),flag(0);
dp[now][c[i]]=dp[last][c[i]]*turn(1.0/(r[c[i]]-i+1));
F(j,c[i]+1,h){
dp[now][j].val=dp[now][j].lg=0;
if(i<r[j]-d&&j>c[i]+d) ++flag;
if(flag>d) break;
dp[now][j]=dp[now][j-1]+dp[last][j];
dp[now][j]=dp[now][j]*turn(1.0/(r[j]-i+j-c[i]+1));
}
}
double res=dp[w&1][h].lg+log2(dp[w&1][h].val);
F(i,1,n)
res+=log2(i);
```
不喜勿喷 0v0~