离散数学课程期末项目-LOJ6519解题报告

链接https://loj.ac/p/6519

主要利用群论-Burside引理、计数原理、容斥原理及一些数论知识解决该问题

题意

对$n$个珠子组成的手环染黑白两种颜色，手环旋转同构但不对称同构。且手环的染色方案要求如下：

  • $n$个珠子中恰好有$m$个黑色珠子和$n-m$个白色珠子

  • 手环不包含任何一段连续的$k+1$个黑色珠子

问有多少种手环染色的方案

解题过程

对于同构求染色方案的题目，容易想到Burnside引理及Polya定理。尝试利用Burnside引理求解。

由于只考虑旋转同构，由Burnside引理，
$$
答案=\frac{\sum_{i=1}^{n}C(i)}n
$$
其中$i$表示顺时针旋转$i$个珠子，$C(i)$表示旋转$i$个珠子时的不动点个数。

当旋转$i$个珠子时，设$d_i=\gcd(n,i)$。若某种着色方案为不动点，则$a_i=a_{i+d_i\pmod n}$，即原手环可以等价为一个长度为$d_i$的小环复制$\frac n {d_i}$次。

因此，对于$i_1$和$i_2$，只要$\gcd(n,i_1)=\gcd(n,i_2)$，则二者对不动点个数的贡献就相同。考虑将这样的$i$一起统计答案。

设$\gcd(i,n)=d$，则当$\frac n d|m$时（黑色珠子的个数需要是小环循环次数的倍数），才可能有合法方案。也即$\frac n d|\gcd(n,m)$

设$f(d)$为小环长度为$d$，使得其中$\frac{md}n$个小球为黑色，且不存在连续$k+1$个黑色珠子的方案数,则
$$
答案=\frac{\sum _ {\frac{n}{d}|\gcd(n,m)}\sum _ {i=1}^{n}[\gcd(n,i)=d]f(d)}n \\
=\frac{\sum _ {\frac{n}{d}|\gcd(n,m)}\sum _ {i=1}^{\frac n d}[\gcd(\frac n d,i)=1]f(d)}n \\
=\frac{\sum _ {\frac{n}{d}|\gcd(n,m)}\varphi(\frac n d) f(d)}n
$$
下面讨论如何求解$f(d)$

首先，对于小环的染色方案数求解，不需要考虑旋转同构的问题。

考虑断环成链。将小环假设成链的情况考虑，再加上首尾的限制。

设首部和尾部连续黑珠之和为$i$，则
$$
\begin{cases}
f(d)=\binom d{\frac{md}n}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~k\le\frac{md}{n}时\\
f(d)=\sum_{i=0}^k (i+1)\cdot g(d-i-2,\frac{md}{n}-i)~~~~~~~~其余情况
\end{cases}
$$
其中$g(x,y)$表示长度为$x$的链上将$y$个珠子染黑且不存在连续$k+1$个黑珠子的方案数。

考虑一种常见的容斥思路，设$z=x-y+1$，即将白球看成板（隔板法）时黑球可插入的位置数
$$
g(x,y)=所有方案-至少出现一个不合法段的方案数+至少出现两个不合法段的方案数-\dots \\
=\sum _ {i=0} ^ {\min(z,\frac{y}{k+1})}(-1)^i\binom z i\cdot h(z,y-i\cdot(k+1))
$$
其中$h(x,y)$表示将$y$个相同的小球放入$x$个不同的盒子中（允许空盒）的方案数，隔板法得：
$$
h(x,y)=\binom{x+y-1}{x-1}
$$
即可在$O(\sum_{d|n}k\cdot\frac{\frac{md}n}k)=O(\sigma(n))$的时间复杂度下求解。其中$\sigma(n)$为约数和函数，且$O(\sigma(n))\le O(n\sqrt n)$http://oeis.org/A000203

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//by Richard
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define mp make_pair
#define rep(x,y,z) for (int x=(y);(x)<=(z);(x)++)
#define per(x,y,z) for (int x=(y);(x)>=(z);(x)--)
#define lowbit(x) ((x)&(-(x)))
#define cls(x) memset(x,0,sizeof(x))
#ifdef DEBUG
#define debugdo(X) X
#define debugndo(X)
#define debugout(X) cout<<(#X)<<"="<<(X)<<endl
#else
#define debugdo(X)
#define debugndo(X) X
#define debugout(X)
#endif // debug
using namespace std;
mt19937 rnd(19260817);
const int inf=0x3f3f3f3f;
const int mod=998244353;
typedef long long LL;
typedef pair<int,int> pii;
///////////////////////read5.1///////////////////////
template<typename T>
inline void read(T &x){char ch;x=0;bool flag=false;ch=getchar();while (ch>'9'||ch<'0') {if (ch=='-') flag=true;ch=getchar();}while ((ch<='9'&&ch>='0')){x=x*10+ch-'0';ch=getchar();}if (flag) x*=-1;}
template<typename T,typename U>
inline void read(T &x,U &y){read(x);read(y);}
template<typename T,typename U,typename V>
inline void read(T &x,U &y,V &z){read(x);read(y);read(z);}
////////////////variables&functions//////////////////
const int maxn=222222;
int n,m,k,gg,prime[maxn],phi[maxn],frac[maxn],inv[maxn],tot;
bool notprime[maxn];
void getphi(int gg)//线性筛计算欧拉函数
{
    phi[1]=1;
    rep(i,2,n)
    {
        if (!notprime[i]) prime[++tot]=i,phi[i]=i-1;
        for (int j=1;j<=tot&&i*prime[j]<=n;j++)
        {
            notprime[i*prime[j]]=1;
            if (i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int power(int x,int y)//计算x的y次幂
{
    int res=1;
    while (y)
    {
        if (y&1) res=(LL)res*x%mod;
        y>>=1;
        x=(LL)x*x%mod;
    }
    return res;
}
int C(int n,int m)//calculate number of combination
{
    if (m>n) return 0;
    if (m==0) return 1;
    return (LL)frac[n]*inv[m]%mod*inv[n-m]%mod;
}
int h(int x,int y)
{
    return C(x+y-1,x-1);
}
int g(int x,int y)//x is total number
{
    x=x-y+1;//x is number of white balls
    int mm=min(x,y/(k+1)),res=0,pos=1;
    rep(i,0,mm)
    {
        res=(res+(LL)pos*C(x,i)%mod*h(x,y-i*(k+1))%mod)%mod;
        pos=-pos;
    }
    res=(res+mod)%mod;
    return res;
}
int f(int d)
{
    if ((LL)k*n>=(LL)m*d) return C(d,(LL)m*d/n);
    int res=0;
    rep(i,0,k) res=(res+(LL)(i+1)*g(d-i-2,(LL)m*d/n-i))%mod;
    return res; 
}
void initfrac(int n)//预处理组合数所需的阶乘和阶乘的逆元
{
    frac[0]=1;
    rep(i,1,n) frac[i]=(LL)frac[i-1]*i%mod;
    inv[n]=power(frac[n],mod-2);
    per(i,n-1,0) inv[i]=(LL)inv[i+1]*(i+1)%mod;
}
int main()
{
    read(n,m,k);
    gg=__gcd(n,m);
    getphi(200000);
    initfrac(200000);
    int ans=0;
    rep(d,1,n) if (n%d==0&&gg%(n/d)==0) ans=(ans+(LL)f(d)*(phi[n/d])%mod)%mod;
    ans=(LL)ans*power(n,mod-2)%mod;
    cout<<ans<<endl;
    return 0;
}