2 条题解

  • 5
    @ 2025-12-10 9:05:40

    科普:环形染色公式(中间不染色)的推导

    我们先把他当链做:这样有 m(m−1)n−1m (m-1)^{n-1} 种做法。

    在变成环,分类讨论:

    1. 11 和 nn 相同这样就有 fn−1f_{n-1} 种方案

    2. 反之,为 fnf_n 种做法

    所以 fn+fn−1=m(m−1)n−1f_n+f_{n-1}=m(m-1)^{n-1} 。

    还可以化:

    $$f_n+f_{n-1}=m(m-1)^{n-1}=(m-1+1)(m-1)^{n-1}=(m-1)^n+(m-1)^{n-1} $$

    移项,得

    fn−(m−1)n=−(fn−1−(m−1)n−1)f_n-(m-1)^n=-(f_{n-1}-(m-1)^{n-1})

    我们令 bn=fn−(m−1)nb_n={f_n-(m-1)^n},你会发现

    bnbn−1=−1\large \frac{b_n}{b_{n-1}}=-1,所以 bb 是个等比数列。

    当 n=2n=2 时,显然,f2=m(m−1)f_2=m(m-1),则

    b2=f2−(m−1)2=m(m−1)−(m−1)2=m−1b_2=f_2-(m-1)^2=m(m-1)-(m-1)^2=m-1

    所以 bn=b2×(−1)n−2=(−1)n×(m−1)b_n=b_2 \times (-1)^{n-2} = (-1)^n\times (m-1)

    又因为 fn=bn+(m−1)nf_n=b_n+(m-1)^n,

    所以 fn=(m−1)n+(−1)n×(m−1)f_n=(m-1)^n+(-1)^n\times(m-1)。

    信息

    ID
    250
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    39
    已通过
    10
    上传者