CF891E

cwy posted @ 2017年12月14日 20:47 in CF , 33 阅读

令人境界飙升的数数题?

首先答案=初始乘积-最终乘积的期望。(易证)

这样写出指数型生成函数的形式后可以ntt做到O(nklogk)。

然后我想到了最终答案的式子应该是这样一些东西xabc+y(ab+ac+bc)+z(a+b+c)+w,就是说不同的系数只有O(n)个,只要通过某些方式获得系数就做完了?

系数可能有规律?不会会啊。。

喵了题解,里面写到了子集DP的做法,然后把接下来的做法自行YY出来了。

大概就是说把DP式子写出来后发现直接可以算每项到第k步的系数,做完了。

总结:因为期望很好加减,所以把状态用子集表示就很好转移。之后就比较显然了?

其实DP只是某种脑子里想的时候用来推出系数的途径罢了,如果会找规律就更棒了?

其实当n一定是时候,系数是关于k的多项式?可能把多项式插出来也可以?

http://codeforces.com/contest/891/submission/33239888

Avatar_small
cwy 说:
2018年1月12日 13:48

Wow! You have "-1" rating changes! Congratulations!


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter