FZU 第十五届程序设计竞赛_重现赛 & FOJ Problem 2289 项链

给定一个 \(m\) 元环与 \(n\) 种颜色，要求给环的每个元素上色，并且相邻元素的颜色不同

题为求解 \(n\) 个颜色填涂 \(m\) 元环的方案数

设方案数为 \(F_m\) ，即表示 \(m\) 元环中，相邻元素颜色不同的方案数

易得 \(F_1=n,F_2=n(n-1),F_3=n(n-1)(n-2)\)

对于 \(n>3\) 的情况，考虑倒数第二个位置是否和开头颜色相同：

1. 当倒数第二个位置是否和开头颜色相同时，则前 \((m-2)\) 个位置需满足相邻元素颜色不同，且倒数第三个的颜色不与倒数第二个相同，即不与开头相同。
   而 \(F_{m-2}\) 表示 \((m-2)\) 元环中，相邻元素颜色不同的方案数，与上面的描述等价。故前 \((m-2)\) 的位置的方案数为 \(F_{m-2}\) 。
   再考虑倒数第二位与开头颜色相同，方案数为 \(1\) ，最后一位与两边相同的颜色不同，方案数为 \((n-1)\) ，故由乘法原理，方案数为 \(F_{m-2}\cdot 1\cdot (n-1)=(n-1)F_{m-2}\)

2. 当倒数第二个位置是否和开头颜色不同时，前 \((m-1)\) 个的方案数，即为相邻元素颜色不同，且倒数第二位颜色不与开头相同。
   而 \(F_{m-1}\) 表示 \((m-1)\) 元环中，相邻元素颜色不同的方案数，与上面的描述等价。故前 \((m-1)\) 的位置的方案数为 \(F_{m-1}\) 。
   再考虑最后一位，其不与两边不同颜色相同，故方案数为 \((n-2)\)。故由乘法原理得，方案数为 \((n-2)F_{m-1}\)

最后我们由加法原理得知， \(F_m=(n-2)F_{m-1}+(n-1)F_{m-2},m>3\)

---

【法一】

\(n=1\) 时特判，否则使用矩阵快速幂：

构造矩阵：\( \left( \begin{matrix} F_m \\\ \\ F_{m-1} \end{matrix} \right)= \left( \begin{matrix} n-2&n-1 \\\ \\ 1&0 \end{matrix} \right)\cdot \left( \begin{matrix} F_{m-1} \\\ \\ F_{m-2} \end{matrix} \right)\)

不难得到 \( \left( \begin{matrix} F_{m+1} \\\ \\ F_m \end{matrix} \right)= \left( \begin{matrix} n-2&n-1 \\\ \\ 1&0 \end{matrix} \right)^{n-2}\cdot \left( \begin{matrix} F_3 \\\ \\ F_2 \end{matrix} \right)\)

由于 \(F_3=n(n-1)(n-2),F_2=n(n-1)\) ，故将中间的矩阵快速幂求出 \((n-2)\) 次方可得到解

【代码】

#include<iostream>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
ll N,M;
struct Matrix{
    ll Num[2][2];
    Matrix() { Num[0][0]=Num[0][1]=Num[1][0]=Num[1][1]=0; }
    Matrix operator * (const Matrix &x) const{
        Matrix y;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    y.Num[i][j]=(y.Num[i][j]+Num[i][k]*x.Num[k][j]%MOD)%MOD;
        return y;
    }
    Matrix pow(ll x){
        Matrix ans,a=*this;
        ans.Num[0][0]=ans.Num[1][1]=1;
        for(;x;x>>=1,a=a*a) if(x&1) ans=ans*a;
        return ans;
    }
};
inline int ans(){
    if(M==1) return N;
    Matrix ans,vec;
    ans.Num[0][0]=N-2;
    ans.Num[0][1]=N-1;
    ans.Num[1][0]=1;
    vec.Num[0][0]=N*(N-1)*(N-2);
    vec.Num[1][0]=N*(N-1);
    return (ans.pow(M-2)*vec).Num[1][0];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    while(cin>>N>>M)
        cout<<ans()<<endl;
    return 0;
}

---

【法二】

考虑到有些丧心病狂的出题人可能会卡常数（虽然这题显然不会），考虑一下别的做法：

由递推式 \(F_m=(n-2)F_{m-1}+(n-1)F_{m-2},m>3\) 可以构造出

\(F_m-(n-1)F_{m-1}=-F_{m-1}+(n-1)F_{m-2}=(-1)^1\cdot [F_{m-1}-(n-1)F_{m-2}],m>3\)

故可得 \(F_m-(n-1)F_{m-1}=(-1)^{m-3}\cdot [F_3-(n-1)F_2],m>3\)

代入可得 \(F_m-(n-1)F_{m-1}=-(-1)^m\cdot [n(n-1)(n-2)-(n-1)n(n-1)]=(-1)^m\cdot n(n-1),m>3\)

移项即可得到 \(F_m=(n-1)F_{m-1}+(-1)^m\cdot n(n-1)=(n-1)[F_{m-1}+(-1)^m\cdot n],m>3\)

故 \(F_m-(-1)^m\cdot (n-1)=(n-1)[F_{m-1}+(-1)^m\cdot n-(-1)^m]=(n-1)[F_{m-1}-(-1)^{m-1}\cdot (n-1)],m>3\)

因此很显然，数列 \(\{F_m-(-1)^m\cdot (n-1)\},m>3\) 是一个等比数列

进而得到 \(F_m-(-1)^m\cdot (n-1)=(n-1)^{m-2}[F_2-(-1)^2\cdot (n-1)]\)

代入 \(F_2=n(n-1)\) 整理得到 \(F_m=(-1)^m\cdot (n-1)+(n-1)^m,m>3\)

式子推出来了，剩下的快速幂即可过

【代码】

#include<iostream>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
inline ll fpow(ll a,ll x){
    ll ans=1;
    for(;x;x>>=1,a=a*a%MOD) if(x&1) ans=ans*a%MOD;
    return (ans+MOD)%MOD;
}
inline ll ans(ll N,ll M){
    if(M==1) return N;
    if(M==2) return N*(N-1);
    return (fpow(-1,M)*(N-1)+fpow(N-1,M))%MOD;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll N,M;
    while(cin>>N>>M)
        cout<<ans(N,M)<<endl;
    return 0;
}