LOJ6519 魔力环()

LOJ6519 魔力环

Problem

用 \(m\) 个黑色珠子和 \(n-m\) 个白色珠子串一个链,其中黑色珠子不会连续出现超过 \(k\) 个。求方案数。

Solution

首先上 Burnside 引理:\(ans=\frac{1}{n}\sum\limits_{i|\gcd(n,m)}F(i)\varphi(\frac{n}{i})\)。

其中 \(i|\gcd(n,m)\) 可以考虑 \(i|m\) 再考虑 \(i|(n-m)\),不难想。

\(F(i)\) 表示长为 \(i\) 的环满足条件的染色。都是套路。

关键都在处理 \(F(i)\)。

\(F(i)\) 可以看作是给 \(i\) 个成环的小球中的 \(\frac{mi}{n}\) 个进行染色。

设 \(f(x,y)\) 表示将 \(x\) 个球中的 \(y\) 个染成黑色的合法方案数(即连续染色不超过 \(k\))。

转化成小球放置问题:在 \(x-y\) 个白球中(且两端之外也能放置)放 \(y\) 个黑球的方案数。

破环成链给我们带来了两端的小球,这让我们很不爽。

于是有了下面这一步转化:

解释:枚举裂开的地方放置的黑球数 \(i\)。把裂开的边界看成一条线,在线的左右放置黑球,并且不考虑旋转等价。那么有 \((i+1)\) 种在裂口放置黑球的方法。

\(T(x,y)\) 表示将 \(x\) 个黑球放进 \(y\) 个盒子里且每个盒子里的球数不超过 \(k\) 个的方案数。

由于在边界放了 \(i\) 个黑球,那么左右白球内部要放 \(y-i\) 个黑球。有 \(x-y\) 个白球,那么有 \(x-y-1\) 个放置位置。

接下来考虑计算 \(T(x,y)\)。

考虑用总方案数减去不合法方案数,因此计算不合法方案数。

对某个盒子强制放进 \(k+1\) 个球,剩下的随便放;对某两个盒子强制放进 \(k+1\) 个球,剩下的随便放……

可以容斥一下算出来,记得乘上二项式系数。\(T(x,y)\) 计算结果见下:

其中的 \(H(x,y)\) 定义如下:(就是个普通的插板法)

计算一下时间复杂度。

第一层枚举 \(F(i)\),\(\gcd(n,m)\) 的约数的规模。

第二层枚举 \(T\),枚举了 \(k\) 次。

第三层枚举 \(H\),考虑与第二层合并,规模超不过 \(x,y\)。

啊能过。

要注意一些特殊情况。

————————

LOJ6519 魔力环

Problem

用 \(m\) 个黑色珠子和 \(n-m\) 个白色珠子串一个链,其中黑色珠子不会连续出现超过 \(k\) 个。求方案数。

Solution

首先上 Burnside 引理:\(ans=\frac{1}{n}\sum\limits_{i|\gcd(n,m)}F(i)\varphi(\frac{n}{i})\)。

其中 \(i|\gcd(n,m)\) 可以考虑 \(i|m\) 再考虑 \(i|(n-m)\),不难想。

\(F(i)\) 表示长为 \(i\) 的环满足条件的染色。都是套路。

关键都在处理 \(F(i)\)。

\(F(i)\) 可以看作是给 \(i\) 个成环的小球中的 \(\frac{mi}{n}\) 个进行染色。

设 \(f(x,y)\) 表示将 \(x\) 个球中的 \(y\) 个染成黑色的合法方案数(即连续染色不超过 \(k\))。

转化成小球放置问题:在 \(x-y\) 个白球中(且两端之外也能放置)放 \(y\) 个黑球的方案数。

破环成链给我们带来了两端的小球,这让我们很不爽。

于是有了下面这一步转化:

解释:枚举裂开的地方放置的黑球数 \(i\)。把裂开的边界看成一条线,在线的左右放置黑球,并且不考虑旋转等价。那么有 \((i+1)\) 种在裂口放置黑球的方法。

\(T(x,y)\) 表示将 \(x\) 个黑球放进 \(y\) 个盒子里且每个盒子里的球数不超过 \(k\) 个的方案数。

由于在边界放了 \(i\) 个黑球,那么左右白球内部要放 \(y-i\) 个黑球。有 \(x-y\) 个白球,那么有 \(x-y-1\) 个放置位置。

接下来考虑计算 \(T(x,y)\)。

考虑用总方案数减去不合法方案数,因此计算不合法方案数。

对某个盒子强制放进 \(k+1\) 个球,剩下的随便放;对某两个盒子强制放进 \(k+1\) 个球,剩下的随便放……

可以容斥一下算出来,记得乘上二项式系数。\(T(x,y)\) 计算结果见下:

其中的 \(H(x,y)\) 定义如下:(就是个普通的插板法)

计算一下时间复杂度。

第一层枚举 \(F(i)\),\(\gcd(n,m)\) 的约数的规模。

第二层枚举 \(T\),枚举了 \(k\) 次。

第三层枚举 \(H\),考虑与第二层合并,规模超不过 \(x,y\)。

啊能过。

要注意一些特殊情况。