BZOJ4361: isn

-------------------------------------------------
 
看了题解之后觉得蛮水的...
首先,假设无视A非降之后就不删了这个限制,那么考虑某个长度为i的不下降序列,他对答案的贡献显然是(n-i)!
然后考虑多算的部分,对于每一个长度为i的序列,他所有的子序列的贡献对应该减掉他的出现次数,但是因为他的长度是是i-k的子序列会被长度是i-k+1的子序列考虑到,所以只需要考虑长度为i-1的子序列
因此如果能求出长度为i的不下降子序列个数g[i],那么答案就是Σ(i=1,n)g[i]*(n-i)!-g[i+1]*(n-i-1)!*i
然后考虑怎么求g[i],设f[i][j]表示以i结尾的长度为j的子序列个数,那么显然有f[i][j]=Σ(1<=k<=i-1且a[k]<=a[i])f[k][j-1]
然后这个可以用树状数组优化一下,最后复杂度是O(n*n*log)
-------------------------------------------------