RainAir
My OI Blog
RainAir
「CF840C」On the Bench

题目大意

给你一个长度为 $n$ 的序列,问你有多少种置换,使得置换后的序列相邻两项的乘积都不是平方数。

题解

这个题目好像比较厉害的样子。。首先把这些数按照是否能组成平方数分组,同一组里都是两两相乘能凑成平方数的,可以证明存在这样的分配方案。
然后我们可以设 $f_{i,j}$ 表示插入了前 $i$ 个组,有 $j$ 个不满足的相邻关系的方案数。
我们令 $tot$ 表示已经填完的个数,$sz$表示这一组的大小,$d$ 表示该次插入隔开了原来多少个组,$k$ 表示将这些数分成了多少组。我们不考虑顺序,能得到转移:
$$f_{i-1,j}* T \to f_{i,j-d+sz-k}$$
其中
$$T = \binom {sz-1} {k-1} \binom j d \binom {tot-j+1} {k-d}$$
然后最后答案乘上每组的阶乘,就好了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/806
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF840C」On the Bench
题目大意 给你一个长度为 $n$ 的序列,问你有多少种置换,使得置换后的序列相邻两项的乘积都不是平方数。 题解 这个题目好像比较厉害的样子。。首先把这些数按照是否能组成平方数分组…
扫描二维码继续阅读
2019-08-28
标签
近期评论