「Codeforces960G」Bandit Blues-分治FFT+第一类斯特林数

发布于 19 天前  34 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codeforces960G」Bandit Blues-分治FFT+第一类斯特林数

Decription

求满足以下条件的长度为 \(n\) 的序列方案数

  1. 从左贪心选最长上升子序列长度为 \(a\)
  2. 从左贪心选最长上升子序列长度为 \(b\)

Solution

考虑把序列分成 \(a+b-2\) 组,从 \(i\) 被选取的数到第 \(i+1\) 个被选取的数前一个位置为一组。那么每一组除了最大值为外都是随意排列,方案数为 \((k-1)!\) 。那么方案数就是用\(n-1\)个数拼出出\(a+b-2\)个环(第一类斯特林数),还要乘上从\(a+b-2\)个环中选出\(a-1\)个放在左边的方案数。

分治FTT即可。

ps:这题的暴力\(O(n^2)\)预处理\(O(1)\)回答询问在hdu4372.这样你就可以连A两题了。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codeforces960G」Bandit Blues-分治FFT+第一类斯特林数


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!