题意
求所有 \(n\) 元逆序对数为 \(k\) 的排列所对应的笛卡尔树中 (每次选区间最小连在父亲下, 再分为左右两部分递归), 求每个位置在所有树中的深度和
\(1 \le n \le 300\)
思路
是设 \(f_k\) 表示逆序对数为 \(k\) 的 \(n\) 排列的数量, 那么其生成函数:
- \[F(x)=\prod_{
- i=0
- }^{
- n-1
- }\sum_{
- j=0
- }^{
- i
- }x^j\]
- (大概就是看一下在前面所有数中的位置)
然后再来看需要求的东西, 深度和即为有多少个父亲.\(i\) 为 \(j\) 的父亲需要满足 \(i\) 是 \([i,j]\) 或 \([j,i]\) 的最小值. 考虑生成函数中的顺序其实可以调换, 我们不一定要按从前到后的顺序来考虑, 也可以先把 \([l,r]\) 区间拿出来考虑内部的逆序对, 再从后往前考虑 \([1,l]\) 考虑对 \([i+1,l]\) 中数的贡献, 在从前往后考虑 \([r+1,n]\) 的数对 \([1,i-1]\) 中的贡献, 对于每一个式子, 都能够构造出与之对应的排列, 也就是说, 只要你是挨着构造的, 且大小关系不产生矛盾, 那一 "项" 对应那一个位置都没问题.
然后单独考虑 \(i,j\) 的父子关系, 若 \(i\) 为 \([i,j]\) 中的最小值, 则 \(i\) 会贡献 \(0\) 个逆序对, 此时 \(i\) 是 \(j\) 的父亲. 若 \(j\) 是 \([i,j]\) 中的最小值, 则 \(j\) 会贡献 \(len-1(j-i)\) 个逆序对. 为了方便, 我们把 \(i,j\) 这个位置贡献的逆序对数目拿出来单独考虑, 即 \(1+x+ \dots +x^{len}\) 那一项除掉. 然后对于前者, 有 \(f[k]\) 个排列, 后者有 \(f[k-(len-1)]\) 个
来自蒟蒻 zjy 的瞎掰, 看的人不会很多, 有耐心看的人可能就我一个, 你们如果真想研究可以去 zsy 大佬 https://www.cnblogs.com/zhoushuyu/p/12082371.html 那儿看看
- #include <bits/stdc++.h>
- int f[300*160],n,k,N,mu,ans[305];
- void reduce(int &x) {x+=x>>31μ}
- void cheng(int k){
- for (int i=N;i>=k;i--) reduce(f[i]-=f[i-k]);
- for (int i=1;i<=N;i++) reduce(f[i]+=f[i-1]-mu);
- }
- void chu(int k){
- for (int i=N;i;i--) reduce(f[i]-=f[i-1]);
- for (int i=k;i<=N;i++) reduce(f[i]+=f[i-k]-mu);
- }
- int main(){
- scanf("%d%d%d",&n,&k,&mu);
- N=n*(n-1)/2;
- f[0]=1;
- for (int i=2;i<=n;i++) cheng(i);
- for (int i=1;i<=n;i++) ans[i]=f[k];// 自己的深度
- for (int i=2;i<=n;i++){
- chu(i);// 此段区间加入的贡献下面重新算
- for (int j=1;j+i-1<=n;j++){
- if (k-(i-1)>=0) reduce(ans[j]+=f[k-(i-1)]-mu);//j+i-1 最小
- reduce(ans[j+i-1]+=f[k]-mu);//j 最小
- }
- cheng(i);
- }
- for (int i=1;i<=n;i++) printf("%d",ans[i]);
- }
后记
大型补 blog 现场 (补不完了)
来源: http://www.bubuko.com/infodetail-3395394.html