题解 P3977 【[TJOI2015]棋盘】

· · 题解

阅读理解题……

所有的东西都是从0开始标号的……因此，也就是说，棋子在中间那行……所以可以打前面一行也可以打后边一行，因此我们只需要状态压缩一行就可以了……

因此合法的方案最多只有64种……考虑到不合法的情况，会更少……

因此可以使用矩阵快速幂优化……(话说为什么n只有10^6啊明明可以开到10^9的)现在来讲如何列dp式子好了

(如果不会矩阵快速幂优化的话可以先去写写其他的题，这里就不讲了)

我们一次填一行棋子dp_{i,j}表示决策到了第i行，j是一个仅在二进制下有意义的数字，j的第p位为0或1表示第i行第p列是否有棋子，当然显然有些j的情况本来就是不合法的，所以先打个表把所有合法的j值打出来

然后我们再把每种状态找出来那么如何状态i能否转移j呢，直接打一个每一种集合可以攻击到的集合的表，然后判断下两个集合是否可以相互攻击到，如果不可以相互攻击到的话，就不可以转移到了

代码方面，为了好写的话，可以把输入的表格转化成二进制集合，然后处理出每种行集合的情况可以攻击的集合，然后就可以快速判断了，注意为了方便，我们假定每个棋子都攻击不到自己……

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=80;typedef unsigned int uit;
int n;int m;int p;int k;uit t[N][N];int up;int bk[N][N];uit ans;
int at[3];int att[3][N];int zt[N];int ct;bool book[N];int lg[N];
struct mar//矩阵类 
{
    uit mp[N][N];
    void operator *=(const mar& b)
    {
        for(int i=1;i<=ct;i++)for(int j=1;j<=ct;j++)t[i][j]=0;
        for(int i=1;i<=ct;i++)
            for(int k=0;k<=ct;k++)
                for(int j=1;j<=ct;j++)
                    t[i][j]+=mp[i][k]*b.mp[k][j];
        for(int i=1;i<=ct;i++)for(int j=1;j<=ct;j++)mp[i][j]=t[i][j];
    }
}tr,res,st;
int main()
{
    scanf("%d%d%d%d",&n,&m,&p,&k);
    for(int i=0;i<3;i++)
    {for(int j=0,t;j<p;j++){scanf("%u",&t);at[i]+=(1<<j)*t;}}at[1]-=(1<<k);
    up=(1<<m);zt[++ct]=0;book[0]=true;//先把表格转化成二进制集合，钦定自己不可以攻击自己的 
    for(int i=1;i<up;i++)//然后处理每个集合可以攻击的集合 
    {
        for(int j=0,p=i;p;p>>=1,j++)
        {
            if((p&1)==0){continue;}
            att[0][i]|=(j<k)?at[0]>>(k-j):at[0]<<(j-k);
            att[1][i]|=(j<k)?at[1]>>(k-j):at[1]<<(j-k);
            att[2][i]|=(j<k)?at[2]>>(k-j):at[2]<<(j-k);
        }
    }
    for(int i=1;i<up;i++){if((i&att[1][i])==0){zt[++ct]=i;}}//判定一下合法的状态 
    for(int p1=1;p1<=ct;p1++)//然后判断两个状态是否可以转移 
    {
        for(int p2=1;p2<=ct;p2++)
        {if((att[2][zt[p1]]&zt[p2])==0&&(att[0][zt[p2]]&zt[p1])==0){tr.mp[p1][p2]++;}}
    }
    for(int i=1;i<=ct;i++){res.mp[i][i]=1;}st.mp[1][1]=1;//矩阵快速幂 
    for(;n;n>>=1,tr*=tr){if(n&1){res*=tr;}}st*=res;
    for(int i=1;i<=ct;i++){ans+=st.mp[1][i];}printf("%u",ans);return 0;//拜拜程序~ 
}