当前位置: 首页 > news >正文

P3977 [TJOI2015] 棋盘题解

题目描述

有个 \(n\)\(m\) 列的棋盘,棋盘上可以放许多棋子。每个棋子的攻击范围是 \(3\)\(p\) 列。输入数据用一个 \(3\times p\) 的矩阵给出了棋子攻击范围的模板,棋子被默认为模板中的第 \(2\) 行,第 \(k+1\) 列,则棋子能攻击到的位置是 \(1\),不能攻击到的位置是 \(0\)。输入数据保证第 \(2\) 行第 \(k+1\) 列的位置是 \(1\)。求在棋子互相不能攻击到的前提下,摆放棋子的方案数,答案对 \(2^{32}\) 取余数。

对于 \(100\%\) 的数据,\(1 \leq n \leq 10^{6}\)\(1 \leq m \leq 6\)

题目分析

\(m\) 很小,考虑状压 \(\text{DP}\)

第一步,状压。对于每一行的摆放棋子的情况,我们用二进制压缩,\(0\) 代表改位置不摆放,反之为 \(1\)

第二步,状态总量简化。首先并非 \([0,2^m-1]\) 都是合法行状态,通过枚举,将合法状态存在一个数组 \(S\) 中,这将是之后 \(\text{DP}\) 转移时的可行方案库!

一个小小的问题是,如何利用给定的棋子攻击范围的模板,来快速判断行状态是否合法?显然,行状态的合法性取决于第二行的攻击模板,但是由于攻击模板是以 \(k+1\) 为基准的,所以我们枚举待判定的行中的所有 \(1\),将攻击模板左移 \(\text{or}\) 右移使得 \(k+1\) 与该位置对齐,判断平移后的攻击模板是否与待判定的行有重叠即可(即按位或结果是否非零),这部分的复杂度是 \(O(m)\) 的,因此第二步的总复杂度为 \(O(m2^m)\)

第三步,\(\text{DP}\)。由于棋子攻击范围的模板只有三行,所以转移只需考虑上一行的情况即可。设 \(dp_{i,j}\) 表示第 \(i\) 行摆放棋子的方案为 \(S_j\) 时,前 \(i\) 行构成的子棋盘的所求方案数。则:

\[dp_{i,j}=\sum\limits_{t = 1}^{|S|}{dp_{i-1,t}[check(S_t,S_j)]} \]

其中求和中的括号为艾弗森括号,\(check(S_t,S_j)\) 表示 \(S_t\) 在上一行是否会与 \(S_j\) 冲突。判断方法由第二步如法炮制即可。\(\text{DP}\) 的总复杂度是 \(O(nm(2^m)^2)\)。预处理 \(check\) 的所有情况则可做到 \(O(n4^m)\),由于 \(n\) 很大,这样的做法是很难通过本题的。

第四步,优化。显然这个算法的瓶颈在于 \(n\),但是如何才能把 \(n\) 优化掉呢?在众多 \(\text{DP}\) 优化中,最常见的对 \(n\) 优化的方法当属矩阵加速(快速幂)。因此我们用矩阵的眼光重新梳理转移式:

\[\begin{pmatrix} dp_{i,1} & dp_{i,2} & \dots & dp_{i,|S|} \end{pmatrix} = \begin{pmatrix} dp_{i-1,1} & dp_{i-1,2} & \dots & dp_{i-1,|S|} \end{pmatrix} \begin{pmatrix} check(S_1,S_1) & check(S_1,S_2) & \dots & check(S_1,S_{|S|}) \\ check(S_2,S_1) & check(S_2,S_2) & \dots & check(S_2,S_{|S|}) \\ \dots & \dots & \dots & \dots\\ check(S_{|S|},S_1) & check(S_{|S|},S_2) & \dots & check(S_{|S|},S_{|S|}) \\ \end{pmatrix} \]

这样,我们答案就为:

\[\begin{pmatrix} 1 & 1 & \dots & 1 \end{pmatrix} \begin{pmatrix} check(S_1,S_1) & check(S_1,S_2) & \dots & check(S_1,S_{|S|}) \\ check(S_2,S_1) & check(S_2,S_2) & \dots & check(S_2,S_{|S|}) \\ \dots & \dots & \dots & \dots\\ check(S_{|S|},S_1) & check(S_{|S|},S_2) & \dots & check(S_{|S|},S_{|S|}) \\ \end{pmatrix}^{n-1} \]

配合矩阵快速幂求解,时间复杂度:\(O(8^m\log n)\)

第五步,小细节。对于取模,由于模数为 \(2^{32}\),只需用 \(\text{unsigned}\) \(\text{int}\) 自然溢出即可。

Code

点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
const int N=1e6+10;
int n,m,p,k,a[4],x,S[74],cnt;
ui Ans;
struct mat {ui a[74][74];int r,c;mat() {memset(a,0,sizeof(a));}
};
mat operator * (mat x,mat y) {mat z;z.r=x.r,z.c=y.c;for(int i=1;i<=x.r;i++)for(int j=1;j<=y.c;j++)for(int k=1;k<=x.c;k++)z.a[i][j]=z.a[i][j]+x.a[i][k]*y.a[k][j];return z;
}
mat ksm(mat x,int y) {mat ret=x;y--;while(y) {if(y&1) ret=ret*x;x=x*x;y>>=1;}return ret;
}
mat G,sta,ans;
bool check1(int u) {for(int i=1;i<=m;i++) {if((u>>(i-1))&1) {if(i-k<0) {if(u&(a[2]>>(k-i))) return false;}else {if(u&(a[2]<<(i-k))) return false;}}} return true;
}
bool check2(int u,int v) {for(int i=1;i<=m;i++) {if((u>>(i-1))&1) {if(i-k<0) {if(v&(a[3]>>(k-i))) return false;}else {if(v&(a[3]<<(i-k))) return false;}}} for(int i=1;i<=m;i++) {if((v>>(i-1))&1) {if(i-k<0) {if(u&(a[1]>>(k-i))) return false;}else {if(u&(a[1]<<(i-k))) return false;}}} return true;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m>>p>>k;k++;for(int i=1;i<=3;i++) {for(int j=1;j<=p;j++) {cin>>x;if(i==2&&j==k) x=0;a[i]|=(x<<(j-1)); }} for(int i=0;i<(1<<m);i++) if(check1(i)) S[++cnt]=i;sta.r=1,sta.c=cnt;G.r=G.c=cnt;for(int i=1;i<=cnt;i++) {sta.a[1][i]=1;for(int j=1;j<=cnt;j++)if(check2(S[i],S[j])) G.a[i][j]=1;}ans=sta*ksm(G,n-1);for(int i=1;i<=cnt;i++) Ans+=ans.a[1][i];cout<<Ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=22565

相关文章:

  • 03. 基本元素
  • 基础整理01:Bode图、PM、GM、极点零点 - 教程
  • [已解决]CUDA error: CUBLAS_STATUS_EXECUTION_FAILED when calling cublasSgemmStridedBatched
  • VMware vCenter Server 7.0U3w 发布 - 集中管理 vSphere 环境
  • VMware Aria Operations 8.18.5 发布,新增功能概览
  • VMware Aria Operations for Logs 8.18.5 发布,新增功能概览
  • 专题:2025医药行业数智赋能与AI应用全景研究报告|附200+份报告PDF、数据仪表盘汇总下载
  • 喵之勇者败北录
  • Windows 作为 Ansible 节点的完整部署流程(含 Docker 部署 Ansible) - 实践
  • 软工
  • 10.1考试T4(swap)题解
  • 基本分段存储管理方式
  • 专题:2025零售数字化与即时零售竞争洞察报告|附130+份报告PDF、数据仪表盘汇总下载
  • 2025/10/1图论
  • 详细介绍:Python 豆瓣TOP250 爬虫类讲解
  • springboot用jar启动能访问,但是打成war,部署到tomcat却访问不到 - 详解
  • 用AirPods控制的创新iPhone游戏:RidePods技术解析
  • oppoR9m电话号码盘对应工程模式
  • 常量
  • Index of /ubuntu-releases/25.10/
  • P10364 [PA 2024] Dzielniki 题解
  • 20251001 之所思 - 人生如梦
  • 25普及联考day6爆炸记
  • unity面向组合开发一:面向对象(OOP)与面向组合(EC)
  • 两级页表
  • 复健。(10月,OI)
  • 实用指南:自动驾驶中的传感器技术55——USS(1)
  • 市场交易反心理特征之三:日内假反转
  • 实用指南:云服务器 + Jenkins 实现项目自动化部署与上线
  • Linux 中awk命令如何统计每行指定字符出现的次数