Description
给长为N的序列A,删数恰到A为非降序列,求删数方案
Solution
先思考大范围(即删出一个长为i的非降序列的方案数)
再通过删去误解得到合法解,即减去存在误删的方案数
因为一个合法的非降序列删去其内一个数任然是合法的序列,即强制构造达到一个合法序列再删除一个元素即可(这里对于删除多个元素的情况有一个小容斥)
Code
1 | include<bits/stdc++.h> |
众生之外,此界之中
给长为N的序列A,删数恰到A为非降序列,求删数方案
先思考大范围(即删出一个长为i的非降序列的方案数)
再通过删去误解得到合法解,即减去存在误删的方案数
因为一个合法的非降序列删去其内一个数任然是合法的序列,即强制构造达到一个合法序列再删除一个元素即可(这里对于删除多个元素的情况有一个小容斥)
1 | include<bits/stdc++.h> |