彩虹（状压dp）

题目link

思路

经典状压 $dp$

用 $[0,7^m)$ 来表示状态每列的涂色状态
注意判断相邻同色的方法！

代码

int qmi(int a,int b){
    
    int res =1;
    while(b){
    
        if(b&1) res = res*a;
        a = a*a;
        b >>= 1;
    }
    return res;
}

int n,m;

vector<int> state;

bool check(int x){
    
    int s = x/7,yu = x%7;
    int len = n;
    int f = 0;
    while(--len){
    
        if((s%7) == yu){
    
            f = 1;
            break;
        }
        yu = s%7, s /= 7;
    }
    if(!f) return true;
    return false;
}
bool judge(int l,int r){
    
    int len = n;
    int st1 = state[l];
    int st2 = state[r];
    int s,t;
    while(len--){
    
        s=st1%7,t=st2%7;
        if(s==t) return false;
        st1/=7,st2/=7;
    }
    return true;
}
int f[11][100005];
signed main()
{
    
    cin >> n >> m;

    int sta = qmi(7,n);
    vector<int> get[sta];
    forr(i,0,sta-1){
    
        if(check(i)) state.push_back(i);
    }

    for(int i = 0 ; i < state.size();i++)
        for(int j = 0; j < state.size();j++)
            if(judge(i,j)) get[i].push_back(j);

    for(int i = 0;i < state.size();i++) f[1][i] = 1;
    forr(i,2,m){
    
        for(int j = 0;j < state.size();j++){
    
            for(auto k:get[j]){
    
                f[i][j]  = (f[i][j]+f[i-1][k]) %mod;
            }
        }
    }
    
    int ans = 0;
      for(int i = 0;i < state.size();i++){
    
        ans =  (ans+f[m][i])%mod;
    }
    cout << ans << endl;
    return 0;
}