Tree Depth
考虑所有长度为(N)有恰好(K)个逆序对的排列。
对于每个位置(i)，求出其在所有满足条件的排列中，在笛卡尔树上的深度和。
对读入的质数( ext{MOD})取模。
(N ≤ 300,K ≤inom{N}{2}, ext{MOD} ∈ [10^8, 10^9 + 9])。
题解
题目对排列的逆序对个数有要求，考虑能顺便计算逆序对个数的构造排列的两种过程：
-
按照权值从小到大构造。构造出(1sim x-1)的相对位置后，决定插入(x)的相对位置。新增的逆序对个数(in [0,x-1])。
-
按照位置从前往后构造。构造出(P_1sim P_{x-1})的相对大小后，决定赋值给(P_x)的相对大小。新增的逆序对个数(in [0,x-1])。
回到这道题。题目要求笛卡尔树上每个节点的深度和，利用期望的线性性转化为(j)是(i)的祖先的方案数。
考虑(j)是(i)的祖先需要满足的条件，(min_{min{i,j}leq kleq max{i,j}}{P_k}=P_j)。显然第二种构造方法更有利于这种形式的计算。
注意到第二种方法能执行的条件只需要当前填放的位置是连续的，所以我们可以改变一下填放顺序。
考虑把插入的过程分成两部分：
-
从(i)开始向(j)的方向，决定每个元素在当前排列中的相对大小。
-
从(i)开始向(j)的反方向，决定每个元素在当前排列中的相对大小。
这样除了需要成为(i)祖先的(j)的区间缩成一个单点之外，每次新产生的逆序对数目区间一定是([0,1] , [0,2] , ⋯ ,[0,N − 1])这样。
-
当(j < i)时，(j)必定产生(0)个逆序对。
-
当(j >i)时，(j)必定产生(j − i)个逆序对。
先假装下标为(i)的每次产生逆序对个数在([0, i − 1])内，做一次(DP)。每次枚举(|j-i|)，撤销掉其本来的贡献；然后枚举(i)计算其对(i)答案的贡献。
注意到这个DP过程的本质是背包，所以可以用多项式计算。用(1+x+x^2+dots+x^i=frac{x^{i+1}-1}{x-1})计算来保证复杂度。
时间复杂度(O(N^3))。
CO int N=301;
int ans[N];
int main(){
int n=read<int>(),K=read<int>();
read(mod);
poly F={1};
for(int d=1;d<n;++d){
F.resize(F.size()+(d+1));
for(int i=(int)F.size()-1;i>=0;--i)
F[i]=add(i-(d+1)>=0?F[i-(d+1)]:0,mod-F[i]);
for(int i=0;i<=(int)F.size()-1-1;++i)
F[i]=add(mod-F[i],i-1>=0?F[i-1]:0);
F.resize(F.size()-1);
}
fill(ans+1,ans+n+1,F[K]);
for(int d=1;d<n;++d){
poly G=F;G.resize(G.size()+1);
for(int i=(int)G.size()-1;i>=0;--i)
G[i]=add(i-1>=0?G[i-1]:0,mod-G[i]);
for(int i=0;i<=(int)G.size()-1-(d+1);++i)
G[i]=add(mod-G[i],i-(d+1)>=0?G[i-(d+1)]:0);
G.resize(G.size()-(d+1));
for(int i=1;i<=n;++i){
if(i-d>=1)
ans[i]=add(ans[i],0<=K and K<(int)G.size()?G[K]:0);
if(i+d<=n)
ans[i]=add(ans[i],0<=K-d and K-d<(int)G.size()?G[K-d]:0);
}
}
for(int i=1;i<=n;++i) printf("%d%c",ans[i],"
"[i==n]);
return 0;
}
暴力实现多项式乘法的时候，意义十分明显。
暴力实现多项式除法的时候，如果保证了能够整除，那么从低位到高位考虑意义比较好想。