【递推】【NOIP模拟】彩灯的问题 Lights

对于前$n-1$层的每一层要做的无非是总数目和本层A的数目，而其中A的数目就是上一层不是A的数目。
递推：

#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
void jin(vector<int> &s){                               //统一进位
    int j=0;
    while(j<s.size()-1){
        s[j+1]+=s[j]/10;
        s[j]%=10;
        j++;
    }
    while(s[j]>=10){
        s.push_back(s[j]/10);
        s[j]%=10;
        j++;                    
    }
}
void print(vector<int> s){                              //打印
    for(vector<int>::reverse_iterator it=s.rbegin();it<s.rend();it++)
        printf("%d", *it);
    printf("\n");
}
vector<int> highMulti(vector<int> s, int m){            //高精乘
    int w=s.size();
    int i=0;
    for(i=0;i<w;i++)
        s[i]*=m;
    jin(s);
    return s;
}
vector<int> highMinus(vector<int> a, vector<int> b){    //高精减
    for(int i=0;i<b.size();i++){
        if(a[i]<b[i]){
            a[i+1]-=1;
            a[i]+=10;
        }
        a[i]-=b[i];
    }
    return a;
}
vector<int> highPlus(vector<int> a, vector<int> b){    //高精加
    int i=0;
    for(i=0;i<b.size();i++)
        a[i]+=b[i];
    jin(a);
    return a;
}
int main(){
    int n, m, k, w;
    scanf("%d%d", &n, &m);
    if(n==1&&m==1){                         //邪恶的特判
        printf("%d\n", 1);
        return 0;
    }
    k=n-1, w=m;                             //k就是换了个下标不用管
    vector<int> wa;                         //然后把m高精度存进这个wa去
    while(w){
        wa.push_back(w%10);                 //倒着存
        w/=10;
    }
    vector<int> a;                          //数列a
    a.push_back(1);
    vector<int> mi;                         //m的幂次
    mi.push_back(1);
    for(int i=0;i<k-1;i++){
        a=highMinus(mi, a);                 //a[i]=m^(i-1)-a[i-1]
        mi=highMulti(mi, m-1);              //mi[i]=mi[i-1]*(m-1)
    }
    vector<int> res=highMulti(highPlus(highMulti(mi, m-2), a), m);
    //res=(mi*(m-2)+a)*m;
    print(res);
    return 0;
}

总的来说还好吧，嗯大概就是这样。

标算

• 设$f(i)$为用 $m$种颜色给$i$盏彩灯着色的方案数， $(i=1,\, 2,\, ...\, n)$。 我们设三盏连续的彩灯依次编号为 $i-1$， $i$，$i+1$。现在分析彩灯 $i-1$与彩灯 $i+1$。
  
  1. 若彩灯$i-1$与彩灯$i+1$颜色不同，则去掉彩灯$i$，则变成用$m$种颜色给$n-1$盏彩灯着色的方案数。即$f(i-1)$。 因为彩灯$i$有$m-2$种情况(它与彩灯$i-1$，$i+1$颜色不同)，所以此时方案数为$(m-2)*f(i-1)$。
  2. 若彩灯$i-1$与彩灯$i+1$颜色相同，则去掉彩灯$i$，并把彩灯$i-1$，$i+1$合并成彩灯$i'$，则变成用$m$种颜色给$i-2$盏彩灯着色的方案数。即$f(i-2)$。 因为彩灯$i$有$m-1$种情况(它与彩灯$i-1$，$i+1$颜色不同)，所以此时方案数为$(m-1)*f(i-2)$。
     
     • 综合1、2得出计算$f(n)$的递归方程式: $$f(n)=(m-2)*f(n-1)+(m-1)*f(n-2).$$
  • 边界条件: 由上述分析过程可以看出满足递归式的$n$必须大于$3$。故必须先求出$f(1)$、$f(2)$、$f(3)$的值。很明显:
    　 $$f(1)=m,\; f(2)=m*(m-1),\; f(3)=m*(m-1)*(m-2).$$
  • 此外，因本题方案数增长很快，因此高精度计算也是必不可少的。