无意识的石子堆 加强版

06/24 09:12
阅读数 31

题意简述:

https://loj.ac/problem/6609

题解:

一看m那么大,模数又刚好可以NTT,肯定就是多项式了
显然每行刚好选\(2\)个,每列选\(0-2\)个。
枚举\(i,j\),表示有\(i\)列选了\(2\)个,\(j\)列选了\(1\)个,明显\(i*2+j=n*2\)
这样计数似乎有些恶心。
不妨转换问题,求有\(2*n\)个位置,每个位置可以填1至i或(-j)至(-1),最后要求每个正数出现2次,负数出现1次的方案数。
方案数(似乎)为\(\frac{(2*n)!}{2^i}\)。但是注意到位置\(2*p-1\)\(2*p\)实际上表示的是一行的石子,因此这两个位置的数不能一样,并且不应该有先后顺序。
对于后一个问题,每一种方案每一对位置会算\(2\)次,最后将答案\(\div 2^n\)即可。
对于前一个问题,容斥。强制选\(k\)对位置相同,贡献为:\(\frac{(-1)^{k}*C_n^k*C_i^k*k!*[2*(n-k)]!}{2^{i-k}}\)






因此答案为:
\(\frac{1}{2^n}\sum_{0\leq i\leq n,j=2*(n-i)}C_m^i*C_{m-i}^j*\sum_{0\leq k\leq i}\frac{(-1)^{k}*C_n^k*C_i^k*k!*[2*(n-k)]!}{2^{i-k}}\)
这式子一副可以NTT的亚子,然后就做完了。

代码:

https://loj.ac/submission/684727

展开阅读全文
ntt
打赏
1
0 收藏
分享
加载中
无意识的石子堆
06/24 09:15
回复
举报
更多评论
打赏
1 评论
0 收藏
1
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部