2.22考试

题目不难

T1做得太慢了，而且T2，T3也显得思维不够灵活

注意复习

 

T1：

n<=2000

f[n],剩n张牌期望次数

f[n]=.....从1~n-1算上方案递推过来

C(n-1,i-1)值域分成i段，

g[i]表示i的全排列中，不存在j<j+1且a[j]+1=a[j]的方案数（不能再合并）

g[n]=n!-∑C(n-1,i-1)*g[i]减去不合法的（不合法的一定相邻，考虑相邻几个）

O(n^2)

用多项式科技可以做到O(nlogn)（g多项式求逆）

 

 

T2：

 

折半爆搜

正解：折半
开一个map，先计算C(11,5)*P(6,6)放进C(11,5)个map，map<%k,ll>
再计算P(11,6)到map里查询

直接dfs+常数优化？

1.压二进制，lowbit快速找最后1

2.sz查找剩余1个数，减少dfs传参

3.剩下最后一个1的时候，直接判掉就不用再递归到0了，省下叶子9e7次

 

 

T3：

 

 

矩阵求和二维前缀差分，推两次等比数列求和

维护修改增加值

离线离散化坐标

cdq或者树状数组套线段树