[数据结构与算法]acwing 3494. 国际象棋(蓝桥杯)

题目：3494. 国际象棋

思路：看了大佬的思路仿写的大佬思路,先遍历列，然后每一列里遍历前两列的状态，符合规则的接着遍历目前的列，然后进行dp操作，最后将f[m][i][j][k]的状态求和即可

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const LL M=1e9+7;
const int Maxn=1<<6;
LL f[110][Maxn][Maxn][30];
int get(int x){
    int sum=0;
    for(;x;x-=(x&(-x)))
        sum++;
    return sum;
}

int main(){
    int n,m,k;
    cin>>n>>m>>k;
    int maxn=1<<n;
    f[0][0][0][0]=1;
    for(int i=1;i<=m;i++){
        for(int a=0;a<maxn;a++){
            for(int b=0;b<maxn;b++){
                if(((b>>2)&a)||((a>>2)&b)) continue;
                else{
                    for(int c=0;c<maxn;c++){
                        if(((b>>2)&c)||((c>>2)&b))continue;
                        if(((a>>1)&c)||((c>>1)&a)) continue;
                        int t=get(c);
                        for(int tt=t;tt<=k;tt++){
                            f[i][b][c][tt]=(f[i][b][c][tt]+f[i-1][a][b][tt-t])%M;
                        }
                    }
                }
            }
        }
    }
    LL sum=0;
    for(int i=0;i<maxn;i++){
        for(int j=0;j<maxn;j++){
            sum=(sum+f[m][i][j][k])%M;
        }
    }
    printf("%lld",sum);
    return 0;
}