题解 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呢，直接打一个每一种集合可以攻击到的集合的表，然后判断下两个集合是否可以相互攻击到，如果不可以相互攻击到的话，就不可以转移到了 代码方面，为了好写的话，可以把输入的表格转化成二进制集合，然后处理出每种行集合的情况可以攻击的集合，然后就可以快速判断了，注意为了方便，我们假定每个棋子都攻击不到自己…… 上代码~ ```C #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;//拜拜程序~ } ``` ```