BZOJ4361: isn
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-------------------------------------------------
看了题解之后觉得蛮水的...
首先，假设无视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)
-------------------------------------------------
评论 (0)
