Solid Dominoes Tilings (轮廓线dp打表 + 容器)

第一步先打一个表，就是利用轮廓线DP去打一个没有管有没有分界线组合数量的表

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + ;

const int maxn = <<;

int dp[][maxn + ];

int ans[][];

int solve(int n, int m){

    if(n * m %  == ) return ;

    memset(dp, , sizeof(dp));

    dp[][] = ;

    int ing = , ed = ;

    for(int i = ; i < n; i ++){

        for(int j = ; j < m; j ++){

            swap(ing, ed);

            memset(dp[ing], , sizeof(dp[ing]));

            for(int sta = ; sta < (<<m); sta ++){

                if(sta & (<<j)) dp[ing][sta&(~(<<j))] = (dp[ing][sta&(~(<<j))] + dp[ed][sta]) % mod;//无添加

                if((sta & (<<j)) == ) dp[ing][sta | (<<j)] = (dp[ing][sta | (<<j)] + dp[ed][sta]) % mod;//加上2*1（竖放）

                if(((sta & (<<j)) == ) && (j != m - )) dp[ing][sta | (<<(j+))] = (dp[ing][sta | (<<(j+))] + dp[ed][sta]) % mod;//加上1*2（横放）

            }

        }

    }

    return dp[ing][];

}

int main(){

    freopen("data.txt", "w", stdout);

    for(int i = ; i < ; i ++)

        for(int j = ; j < ; j ++)

            ans[i][j] = solve(i, j);

    for(int i = 0; i < ; i ++){

        for(int j = 0; j < ; j ++)printf("%d, ",ans[i][j]);

    }

    return ;

}

然后用容器原理加上枚举列当前分界线情况去递推容斥。具体如代码：

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const LL mod=1e9+;

LL dp[][]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};

LL f[];

int b[],cnt,siz,n,m;

LL solve(int n,int m){

    LL ret = ;

    for(int sta = ; sta < ( << (m - )); sta ++){

        int cnt = , len = ;

        for(int i = ; i < m - ; i ++){

            len ++;

            if(sta >> i & ){

                b[cnt ++] = len;

                len = ;

            }

        }

        b[cnt ++] =  ++len;

        for(int i = ; i <= n; i ++){

            for(int j = ; j < i; j ++){

                LL temp = ;

                for(int k = ; k < cnt; k ++)

                    temp = temp * dp[b[k]][i - j] % mod;

                if(!j) f[i] = temp;

                else f[i] = ( (f[i] - f[j] * temp % mod) % mod + mod ) % mod;

            }

        }

        if(!(cnt&)) ret = ( (ret - f[n]) % mod + mod ) % mod;

        else ret = (ret + f[n]) % mod;

    }

    return ret;

}

int main(){

    while(~scanf("%d%d",&n,&m)) printf("%lld\n",solve(n,m));

    return ;

}