（Lineup the Dominoes筛子）三维状压

描述:\(一堆筛子，每个筛子两个面，上面有1-6之间的数字。后一个筛子与前一个筛子的接触面的点数必须相等。\)

\(求，有多少种方案堆完筛子。(方案只关心筛子的位置，不关心是否翻转)\)

\(dp[mask][last][orientation]\)，表示使用\(mask\)指示的子数组，以第\(last\)个多米诺骨牌为结尾的合法排列的方法

\(orientation\)多米诺骨牌的状态，0表示原来的方向，1表示翻转。

如果\(mask\)使用二进制表示为01010101，表示使用第0,2,4,6个多米诺骨牌排列而成,1代表使用这个位置上的数组，0代表不使用。

那么，我们先枚举所有状态，再从状态中枚举两个被用过的筛子\(last\)和\(i\)

假设last是结尾用的筛子，那么尝试接到筛子\(i\)上去

如果i和last都是原来的方向：

\(dp[mask][last][0] =sum (dp[mask][last][0],dp[premask][i][0])。\)

如果i是翻转的，last是原来的方向：

\(dp[mask][last][0] =sum (dp[mask][last][0],dp[premask][i][1])。\)

如果i是原来的方向，last是翻转的方向：

\(dp[mask][last][1] =sum (dp[mask][last][1],dp[premask][i][0])。\)

如果i和last都是翻转的方向：

\(dp[mask][last][1] =sum (dp[mask][last][1],dp[premask][i][1])。\)

最后只要将所有\(dp[1<<n-1][i][0]\)和\(dp[1<<n-1][i][1]\)累加所得即可（当\(s[i]==t[i]\)时不用加\(dp[1<<n-1][i][1]\)）。

特殊情况——如果所有的多米诺骨牌都是一样的，那么所有的顺序都是有效的，即全排列。

自己仿照标称的代码

标程

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=1e9+7;

int s[20],t[20];

ll p[25];

ll dp[70000][20][2];

int main()

{

    int T,i,mask,last,n;

    p[0]=1;

    for(i=1;i<=20;i++)p[i]=p[i-1]*i%mod;

    scanf("%d",&T);

    while(T--)

    {

        int fl=0;

        scanf("%d",&n);

        for(i=0;i<n;i++)

            scanf("%d%d",&s[i],&t[i]);

        for(i=1;i<n;i++)

            if((s[i]==s[0]&&t[i]==t[0])||(s[i]==t[0]&&t[i]==s[0])){}

            else {fl=1;break;}

//        特殊情况——如果所有的多米诺骨牌都是一样的，那么所有的顺序都是有效的。

        if(fl==0)

        {

            printf("%lld\n",p[n]);

            continue;

        }

        memset(dp,0,sizeof dp);

        //初始化，表示每个骨牌都有一个初始状态

        for(i=0;i<n;i++)

            dp[1<<i][i][0]=dp[1<<i][i][1]=1;

        for(mask=3;mask<(1<<n);mask++)

        {

            for(last=0;last<n;last++)

            {

                if((mask&(1<<last))==0)continue;

                int premask=mask-(1<<last);

                for(i=0;i<n;i++)

                {

                    if((premask&(1<<i))==0)continue;

                    //i和last都是原来的方向

                    if(t[i]==s[last])

                        dp[mask][last][0] = (dp[mask][last][0]+dp[premask][i][0])%mod;

                    //i是翻转的，last是原来的方向

                    else if(s[i]==s[last])

                        dp[mask][last][0] = (dp[mask][last][0]+dp[premask][i][1])%mod;

                    //i是原来的方向，last是翻转的方向

                    if(t[i]==t[last])

                        dp[mask][last][1] = (dp[mask][last][1]+dp[premask][i][0])%mod;

                    //i和last都是翻转的方向

                    else if(s[i]==t[last])

                        dp[mask][last][1] = (dp[mask][last][1]+dp[premask][i][1])%mod;

                }

            }

        }

        //计算所有可能的情况

        ll ans=0;

        for(i=0;i<n;i++)

        {

            ans=(ans+dp[(1<<n)-1][i][0])%mod;

            if(s[i]!=t[i])//特殊情况不再统计

                ans=(ans+dp[(1<<n)-1][i][1])%mod;

        }

        printf("%lld\n",ans);

    }

}

巴特西

（Lineup the Dominoes筛子）三维状压

最新文章

热门文章