UVA11538 Chess Queen

简要题意

给你一个 \(n\times m\) 的棋盘,你需要在棋盘上放置两个颜色不同的皇后,使得它们互相攻击。求方案数。

\(1 \leq n,m \leq 10^6\)

思路

下面假设 \(n\leq m\)

首先发现,两个互相攻击的皇后大致有下面三种情况:

  • 在同一行,方案数为 \(\binom{n}{1}\operatorname{A}^{2}_{m}=nm(m-1)\)
  • 在同一列,方案数为 \(\binom{m}{1}\operatorname{A}^{2}_{n}=nm(n-1)\)
  • 在同一个斜线上,这个比较复杂:

设所在的斜线的长度为 \(S\),则方案数为 \(2A^{2}_{S}=2S(S-1)\)(因为斜线方向有两种)。

斜线长度一共有:

\[1,2,\cdots,n-2,n-1,\underbrace{n,n,\cdots,n,n}_{m-n+1},n-1,n-2,\cdots,2,1 \]

所以同一个斜线的方案数就是:

\[\begin{aligned} &2(n(n-1)(m-n+1)+2\sum_{i=1}^{n-1}{i(i-1)})\\ &=2(n(n-1)(m-n+1)+2(\sum_{i=1}^{n-1}i^2-\sum_{i=1}^{n-1}i))\\ &=2(n(n-1)(m-n+1)+2(\frac{n(n-1)(2n-1)}{6}-\frac{n(n-1)}{2}))\\ &=2(n(n-1)(m-n+1)+2(\frac{n(n-1)(2n-4)}{6}))\\ &=2(n(n-1)(m-n+1)+\frac{n(n-1)(2n-4)}{3})\\ &=2\cdot\frac{3n(n-1)(m-n+1)+n(n-1)(2n-4)}{3}\\ &=2\cdot\frac{n(n-1)(3m-3n+3+2n-4)}{3}\\ &=\frac{2n(n-1)(3m-n-1)}{3} \end{aligned} \]

于是这道题就做完了。最后答案是:

\[nm(m-1)+nm(n-1)+\frac{2n(n-1)(3m-n-1)}{3} \]

单次计算时间复杂度 \(O(1)\)

代码

点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n,m;

signed main(){
    while(cin>>n>>m&&n&&m){
        if(n>m) swap(n,m);
        int row=n*m*(m-1);
        int col=m*n*(n-1);
        int xie=2*n*(n-1)*(3*m-n-1);
        xie/=3;
        cout<<(row+col+xie)<<'\n';
    }
    return 0;
}
如果文章有问题,静待斧正,建议向我(@xiezheyuan)发送洛谷私信并指出博文地址 http://www.cnblogs.com/zheyuanxie/p/uva11538.html !
本文转载于网络 如有侵权请联系删除

相关文章

  • PQ-M及函数:错误处理语句 try ... otherwise ...,跟Excel里的IFERROR就是一样的

    小勤:大海,我这里有个表的日期转换出错了,怎么办?大海:我看一下什么情况?小勤:你看,我上载数据,然后转换为日期:你看,这里出错了:大海:你这个当然会出错了。首先说啊,像这个表里,最好将这种附加的信息和日期分开,单独成一列。小勤:嗯,但同事给过来就已经这样了,怎么办?我记得Excel里有个IFERROR函数,是不是可以用?大海:嗯。PowerQuery里也有类似的处理办法,但不是一个用函数,是一个语句,功能和Excel里的IFERROR函数一样,叫try…otherwise…语句,可以理解为”试一下…如果出错就…”。小勤:啊。意思倒挺顺。大海:嗯。回到你这个例子,可以添加自定义列,然后写:=try[发货日期]otherwisenull,即“试一下取发货日期的值,如果出错就用null”。看,结果出来了。小勤:嗯。这个写法其实跟Excel里的IFERROR很像啊,IFERROR也是2个参数。大海:对的。另外,其实就你这个问题,可以直接将错误值替换为null。方法如下:这样也好了:小勤:啊。这个更方便。不过我觉try…otherwise…的使用也要学一下,就像在Excel里的IFERROR函

  • 技巧:配置samba使windows共享linux文件

    安装sambaapt-getinstallsamba iferrortry: sudoapt-getinstallsamba=2:4.1.6+dfsg-1ubuntu2samba-common=2:4.1.6+dfsg-1ubuntu2samba-libs=2:4.1.6+dfsg-1ubuntu2samba-common-bin=2:4.1.6+dfsg-1ubuntu2samba-dsdb-modules=2:4.1.6+dfsg-1ubuntu2python-samba=2:4.1.6+dfsg-1ubuntu2libldb1=1:1.1.16-1python-ldb=1:1.1.16-1复制编辑配置文件vim/etc/samba/smb.conf添加下面的内容:[global] unixextensions=yes maparchive=no ntaclsupport=no ..... [share] path=/home/yzh/workspace browseable=yes writable=yes comment=smbsharetest复制添加samba的用户名据

  • 忘记 MySQL Root 用户密码

    因为长时间未使用MySql导致忘记了root密码,现在将修改root用户密码的方法记录下来。修改配置vi/etc/my.cnf复制在[mysqld]中添加skip-grant-tables例如:[mysqld] skip-grant-tables datadir=/var/lib/MySQL socket=/var/lib/mysql/mysql.sock复制重启mysqlservicemysqlrestart复制用户无密码登录mysql-uroot-p(直接点击回车,密码为空)复制选择数据库并修改密码usemysql; updateusersetauthentication_string=password('123456')whereuser='root'; flushprivileges;复制删除并重启mysql服务这个时候发现,确实可以用新的密码登录了,但是操作的时候会提示:ERROR1820(HY000):YoumustresetyourpasswordusingALTERUSERstatementbeforeexecutingthiss

  • scrapy爬取1024种子

    1024不必多说,老司机都懂,本文介绍scrapy爬取1024种子,代码不到50行!Scrapy,Python开发的一个快速、高层次的屏幕抓取和web抓取框架,用于抓取web站点并从页面中提取结构化的数据。Scrapy用途广泛,可以用于数据挖掘、监测和自动化测试。关于scrapy用下图来说明即可(图片来自https://cuiqingcai.com/3472.html)scrapy最好的方式通过官方文档,以及社区贡献的中文文档去学习,使用起来也非常简单,当然功能非常强大!首先创建scrapy项目、CaoliuSpider,下面是创建的爬虫代码:#-*-coding:utf-8-*- importscrapy importjson fromLiosScrapy.itemsimportCaoLiuItem fromscrapy.http.requestimportRequest importsys classCaoliuSpider(scrapy.Spider): #爬虫名称 name='caoliu' #涉及到敏感网站地址 allowed_domains=[

  • 强化学习(一)模型基础

        从今天开始整理强化学习领域的知识,主要参考的资料是Sutton的强化学习书和UCL强化学习的课程。这个系列大概准备写10到20篇,希望写完后自己的强化学习碎片化知识可以得到融会贯通,也希望可以帮到更多的人,毕竟目前系统的讲解强化学习的中文资料不太多。    第一篇会从强化学习的基本概念讲起,对应Sutton书的第一章和UCL课程的第一讲。1. 强化学习在机器学习中的位置    强化学习的学习思路和人比较类似,是在实践中学习,比如学习走路,如果摔倒了,那么我们大脑后面会给一个负面的奖励值,说明走的姿势不好。然后我们从摔倒状态中爬起来,如果后面正常走了一步,那么大脑会给一个正面的奖励值,我们会知道这是一个好的走路姿势。那么这个过程和之前讲的机器学习方法有什么区别呢?    强化学习是和监督学习,非监督学习并列的第三种机器学习方法,从下图我们可以看出来。    强化学习来和监督学习最大的区别是它是没有监督学习已经准备好的训练数据输出值的。强化学习只有奖励值,但是这个奖励值和监督学习的输出值不一样,它不是事先给出的,而是延后给出的,比如上面的例子里走路摔倒了才得到大脑的奖励值。同时,强

  • 「镁客晚报」苹果自家应用AppStore排名作假,IBM令巴菲特亏损20亿美元

    1、苹果被曝在AppStore排名中作弊,iOS9.1强推自家应用 外媒报道,苹果出品的软件包括iWork系列办公应用、iLife系列多媒体处理软件等,升级iOS9.1之后,在iOS的应用商店中,这些免费应用的排名进入前20热门榜单,但在榜单中的位置并不固定,而在电脑版中这些应用并未出现在免费应用前20的热门榜单中。 经过外媒测试,在iPhone5S和iPhone6S中,即便同样是最新的iOS9.1系统,排名也不尽相同,例如Pages在iPhone5s的20大应用排行榜中位列第7,而在6s中却位列第6。Numbers在5s中排名第9,在6s中排名第10。iTunesU在5s中排名11,在6s中排名13。 2、苹果欲在新加坡走清洁能源路线,转向太阳能 11月17日早间消息,苹果已达成协议,在扩大新加坡业务运营的过程中采用太阳能。目前,苹果正计划在全球范围内加强对清洁能源的利用。新加坡屋顶太阳能装置提供商SunseapGroup表示,从明年1月开始,苹果将从该公司采购40千兆瓦时的能源。该公司负责人劳伦斯·吴(LawrenceWu)表示:“除了位于宏茂桥的办公室之外,2016年苹果还将在新

  • 虚拟网络中可视性平面提高性能和安全性

    软件定义网络(SDN)和网络功能虚拟化(NFV)可以带来很多好处,但增加网络抽象层是有代价的:对物理层链路的流量的可视性。同时,越来越快的网络也加剧了这一挑战,因为现在几乎没有网络监控、管理或安全工具可以在40Gbps或100Gbps运行。网络数据包中转(NPB),也被称为网络可视性控制器,它可以通过捕捉、过滤、聚合和优化流量来解决这个挑战。这可以使1Gbps和10Gbps性能管理和安全系统在40/100Gbps网络运行。但这些物理NPB能否有效在虚拟网络基础设施运行?并且,NPB功能本身是否可以虚拟化以用于软件定义网络中的“白盒”交换机吗?第一个问题的答案取决于用于创建虚拟网络流量的工具和协议的要求。很多网络和应用性能管理及安全工具需要从物理链路的总流量隔离个别流量或会话。为了适应这一需求,NPB一直支持各种网络分段、封装和隧道协议,例如虚拟局域网、多协议标签交换和GPRS隧道协议。但比这些协议(特别是协议生态系统不断发展)更重要的是能够在2层网络到7层网络检测和识别数据包,还有可以灵活地配置和编程NPB来剥离和切片数据包以优化监控应用程序,以及支持新兴协议,例如VXLAN。NPB必

  • Golang语言社区--Go操作CSV文件

    大家好,我是Golang语言社区主编彬哥;今天给大家讲解一篇关于Go语言操作CSV文件的相关的。读取CSV文件如下:读取的函数:puck.csv读取函数: //globalData数据结构所在目录 packageGlobal_Define //csv配置表 varG_StCard2InfoBaseSTmap[string]*Card2InfoBase//卡牌活动结构 //卡牌活动结构 typeCard2InfoBasestruct{ Card2IDstring//卡牌的ID Card2Msgstring//卡牌的描述 Card2GameNamestring//卡牌的地点 Card2GameIDstring//策划看到的类型 PicPathstring//图片路径 Typestring//卡牌类型 } -------------------------------------------------- packagemain import( "项目目录/globalData" "encoding/csv" "fmt

  • 虚拟性爱技术,与人无关?(上)

    房事是非多。从进化心理学的角度,人在进化中不断追求性和繁衍。性和繁衍上有优势的个体会被自然选择挑中,获得更强的基因延续。弗洛伊德把这种性和快感的本能称为“力比多”,并把它定义为人类心理现象发生的驱动力。在过去,性的满足基本意味着和异性交配。自然界给了人类一种默契:在和异性身体的接触中,总能收获最美妙的性爱体验。在这么多年时间里,性行为和生物性繁衍,可以说是一回事。而到了今天这个时代,智能机器和可计算性爱的出现,让身体在性爱方面得天独厚的吸引力,也许会逐步让位于精细化的性爱机器。而繁衍也可以和人不相关,想象一下在和机器性爱的过程中,同时完成试管婴儿的植入。在这种情况下,人类是否会把虚拟性爱看作繁衍的变种,并认为满足了基因延续需求?英国生物学家道金斯在《自私的基因》中大胆阐述了一个观点:任何生物,都是求生的机器,都是为了基因的延续。考虑到在性爱和繁衍上,机器很可能在体验和成功率都比真人有更大优势。那么人在追求性和繁衍的时候,在机器介入后会发生什么变化?前些时间果壳网出了一篇文章《你会爱上一个机器人,并和Ta做爱做的事情吗?》,从历史和电影的角度阐释了人和机器的性爱想象。在今天的这篇文章里,

  • 5000 万、人保财险私有云单一来源:腾讯云

    2022年6月17日, 中国人民保险集团股份有限公司发布《关于人保财险2022年私有云服务项目拟采用单一来源方式采购的公示》。单一来源供应商:腾讯云计算(北京)有限责任公司(原厂商)、北京富通东方科技有限公司(原厂商指定代理商)中标结果 2022年9月23日发布中标结果,腾讯云计算(北京)有限责任公司(原厂商)、北京富通东方科技有限公司(原厂商指定代理商)中标。合同确定的采购数量:不适用成交价(含税):5000万元(按实际用量据实结算) 相关阅读 ·中国人保财险1.24亿维保大单:其中IBM8080万 人保财险2022年私有云单一来源:腾讯云 人保财险安全设备采购:天融信、启明星辰、浪潮、方德信安、安恒、中科软、信诺时代、银信长远中标 7735万元、中国人保财险「存储、服务器」采购:新华三6016万元、信利恒丰1719万元

  • Android之 -WebView实现离线缓存阅读

    前言 本篇博客要实现的是一个离线下载和离线阅读的功能,这是很多阅读类app都常见的一个功能,典型的应用就是网易新闻。什么是离线下载?其实这个概念是比较模糊,是离线之后下载呢,还是下载之后离线,但稍微有点脑子的人都知道没有网络之后怎么下载呢?所以离线下载这个功能是”在有网络的情况下,把资源下载到本地“,离线阅读就是”在没有网络或者网络不好的时候,阅读本地好缓存的文章资源“。这样就很清楚我们要的这两个具体的功能需求了。 实现思路 小巫这里提供两个实现思路,一个就是自己写逻辑,一个是通过WebView本身自带的缓存功能来实现。先来说第一个思路: 定义一个离线下载的服务Service 启动后台服务Service来执行异步下载 存储到本地数据库中 每一次加载url之前,先判断数据库是否存在缓存内容5.如果存在缓存,优先加载本地缓存,如果不存在,才执行联网请求 第二个思路就是本篇博客要讲的通过WebView自带的缓存功能来实现离线阅读这里小巫接着上一篇博客的例子来添加代码。 参考1:http://www.open-open.com/lib/view/open1392188052301.htm

  • 软件架构实践阅读笔记3

    软件架构实践阅读笔记3 时间: 2020-06-01 第三部分是分析架构 在构架商业周期中,设计师已经设计了构架并将其编成了文档。现在的任务是,讨论如何评估和分析构架,以确保该构架满足了需求,能够正常发挥作用。这就是第田部分的重点,我们首先回答关于构架评估的一些基本问题一原因、 时间、成本、收益、技巧、计划内、计划外、前置条件及结果。 那么为什么我们要分析架构呢 因为关于系统构架的一个最重要的事实是,可以通过了解构架获知系统本身的重要属性即使系统还不存在。设计师要制定设计决策,这些决策将会对他们构建的系统产生下游影响,这些影响是可知的并且是可预测的。如果不制定设计决策的话,那么,设计构架的过程几乎就是在掷骰子:我们只是随机选择了一个构架,然后根据该构架构建系统,看看系统是否具有所期望的属性:如果没有,回过头来重新进行设计。然而,构架不是烹饪技术,我们知道自己可以比随机猜想做得更好。设计师大体上知道其设计决策将会产生的影响。正如在第5章所看到的,我们尤其可以通过使用构架战术和模式使采用该构架的系统具有某些已知的属性。因此,设计选择(也就是构架)是可以进行分析的。给定-

  • oracle

    一.什么是oracle分区,什么时候用,通常有哪几种类型 (1)分区的实质是把一张大表的数据按照某种规则使用多张子表来存储。 然后这多张子表使用统一的表名对外提供服务,子表实际对用户不可见。类似于在多张子表上建立一个视图然后用户直接使用该视图来访问数据。 (2)Oracle分区在什么情况下使用 当一张表的数据到达上亿行的时候,表的性能会严重降低,这个时候就需要用到分区了,通过划分成多个小表,并在每个小表上建立本地索引可以大大缩小索引数据文件的大小从而更快的定位到目标数据来提升访问性能。 分区除了可以用来提升访问性能外还因为可以指定分区所用的表空间,因此也用来做数据的生命周期管理当前需要繁使用的活跃数据可以放到访问速度更快但价格也更贵的存储设备上,而2、3年前的历史数据,或者叫冷数据可以放到更廉价、速度更低的设备上。从而降低存储用。 (3)Oracl的分区可以分:列表分区、范围分区、散列分区(哈希分区)、复合分区。    列表分区   1)、列表分区明确指定了根据某字段的某个具体值进行分区,而不是像范围分区那样根据字段的值范围来分的。   

  • JSP九大内置对象

    内置对象是什么?     不用new也能使用的对象。   1.out       输出对象,向客户端输出内容   2.request     请求对象,储存客户端向服务端发送的请求信息      request常见方法:       StringgetParameter(Stringkey) 请求字段key,返回对象value       String[]getParameterValues(Stringkey),根据请求对象key,返回对象的values。常见于checkbox       voidsetCharacterEncoding("utf-8"),设置字符编码       getRequestDispatcher("b.jsp").forward(request,response)从当前界面跳转到b界面       ServletContext getServerContext();获取项目的ServletContext对象   3.response:响应对象,服务端向客户端响应     常见方法:       voidaddCookie(Cookiecookie)服务端想

  • [C#] winform中的DataGridView的列宽设置(自动调整列宽)

    [C#]winform中的DataGridView的列宽设置(自动调整列宽)     找了很多都说DataGridView有一个属性AutoSizeColumnMode,他有很多枚举值: 1、AllCells调整列宽,以适合该列中的所有单元格的内容,包括标题单元格。  2、AllCellsExceptHeader调整列宽,以适合该列中的所有单元格的内容,不包括标题单元格。  3、ColumnHeader调整列宽,以适合列标题单元格的内容。  4、DisplayedCells调整列宽,以适合当前屏幕上显示的行的列中的所有单元格的内容,包括标题单元格。  5、DisplayedCellsExceptHeader调整列宽,以适合当前屏幕上显示的行的列中的所有单元格的内容,不包括标题单元格。  6、Fill调整列宽,使所有列的宽度正好填充控件的显示区域,只需要水平滚动保证列宽在DataGridViewColumn.MinimumWidth属性值以上。相对列宽由相对Dat

  • 两个路由器配置静态路由只能单边 ping 通

    一、问题描述 两个路由器上都配置了静态路由,互相都能ping通下一跳地址; 但3网段主机无法ping通101网段,101网段可以ping通3网段主机。 二、问题解决 先检查路由器防火墙问题,发现都没有开启,路由器也都允许ping; 经排查判断应该是在华三路由器出了问题,通过配置发现华三下一跳接口配置了nat功能。 interfaceGigabitEthernet0/4 portlink-moderoute natoutbound ipaddress192.168.2.3255.255.255.0 tcpmss1024 复制 把华三下一跳接口nat关闭,两个局域网就可以互通了。 interfaceGigabitEthernet0/4 undonatoutbound 复制 三、总结 原因是下一跳端口做了nat功能,在华三路由器上192.168.101.0/24这个相当于内网地址; 而192.168.3.0/24相当于外网地址了,内网地址能通外网,但是外网ping不通内网。 作者:神奇二进制 文章出处:https://www.cnblogs.com/l-hh/ 本文版

  • 学习资料汇总

    这是我在学习过程中看到的、找到的一些比较好的资料。 有些已经学过防止以后遗忘把资料列在这里,还有些没有开始留着以后学习,总之统一整理在这里方便回顾。 一.数学 线代:MIT的GilbertStrang的线性代数课程 概率论与统计:《概率论与数理统计》陈希孺 二.python入门 南大python课程-用python玩转数据 嵩天Python数据分析与展示 廖雪峰Python教程 莫烦python教程 三.机器学习入门 1.课程 吴恩达老师的Coursera机器学习课程 课程对应的中文笔记 课程编程作业没有用python,推荐一个课程作业的python实现。 林轩田老师的机器学习基石,机器学习技法 推荐这两门课的笔记 2.理论书籍 《统计学习方法》 《机器学习》 3.实践书籍 《Hands-OnMachineLearningwithScikit-LearnandTensorFlow》 《机器学习实战基于sklearn与Tensorflow》中文版 《机器学习实战》 四.深度学习入门 1.课程 deeplearning.ai系列课程; 搭配两个中

  • 【GMT43智能液晶模块】例程十三:FATFS实验——文件操作

    实验原理:   STM32F429上带有SDIO控制器,GMT43液晶模块上将SDIO连接到TF卡座。本实验 将MicroSD卡插入TF卡座上即可。通过FATFS创建test.txt文件,并且写入数据0-255,然后 读出并显示在液晶屏上。 示例截图: 源代码下载链接: 链接:https://pan.baidu.com/s/1raoiNl6密码:5w39 GMT43购买链接: 核心代码:     intmain(void) { FRESULTres; rcc.initialize(); ads7843.initialize(); SDRAM_Init(); SDRAM_GPIOConfig(); FMC_SDRAMWriteProtectionConfig(FMC_Bank2_SDRAM,DISABLE); lcd_tft.initialize(); systick.initialize(); GUI_Init(); GUI_SetBkColor(GUI_BLACK); GUI_Clear(); pwm.initialize(80); GUI_Del

  • 数组拷贝

    1importjava.util.Arrays; 2 3publicclassTest01{ 4publicstaticvoidmain(String[]args){ 5//数组拷贝方式1 6//int[]a={1,2,3,4,5}; 7//int[]b=newint[a.length]; 8//for(inti=0;i<a.length;i++){ 9//b[i]=a[i]; 10//} 11//for(inti=a.length-1,j=a.length/2;i>=a.length/2;i--,j++){ 12//b[j]=a[i]; 13//} 14//System.out.println(Arrays.toString(b)); 15 16//---------------------------- 17//数组拷贝方式2,Arrays.copyOf(要拷贝的原始数组,要拷贝的元素个数) 18//int[]a=newint[]{1,2,-3,4,5}; 19//int[]b=Arrays.copyOf(a,a.length); 20//System.out.prin

  • 归并排序——Merge Sort

    基本思想:参考 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。首先考虑下如何将2个有序数列合并。这个非常简单,只要从比较2个数列的第一个数,谁小就先取谁,取了后就在对应数列中删除这个数。然后再进行比较,如果有数列为空,那直接将另一个数列的数据依次取出即可。 //将有序数组a[]和b[]合并到c[]中 voidMemeryArray(inta[],intn,intb[],intm,intc[]) { inti,j,k; i=j=k=0; while(i<n&&j<m) { if(a[i]<b[j]) c[k++]=a[i++]; else c[k++]=b[j++]; } while(i<n) c[k++]=a[i++]; while(j<m) c[k++]=b[j++]; }复制   解决了上面的合并有序数列问题,再来看归并排序,其的基本思路就是将数组分成2组A,B,如果这2组组内的数据都是有序的,那么就可以很方便的将这2组数据进行排序。如何让这2组组内数据有序了?可以将A,B组

  • 对MySQL库、表和记录的基本操作

    目录对MySQL库、表和记录的基本操作对库的简单操作创建库(增)修改库(改)查看库(查)切换库(切换)修改库名的一个小脚本(修改库名)删除库(删)对表结构的简单操作创建表(增)修改表(改)查看表(查)复制表(复制)删除表(删)对记录的简单操作创建记录(增)修改记录(改)查看记录(查)删除记录(删) 对MySQL库、表和记录的基本操作 对库的简单操作 创建库(增) #创建库,charset指定编码格式。[]中为可选项 createdatabase库名[charsetutf8] createdatabasedb1;#创建db1库 createdatabaseusercharsetutf8;#创建user库 复制 注意:创建数据库时指定字符编码,不能写utf-8 修改库(改) alterdatabase库名charset新的编码方式;#修改库的编码方式 alterdatabasedb1charsetgbk;#修改为gbk ALTERDATABASEUsercharsetgbk;#修改为gbk 复制 查看库(查) showdatabases;#查看所有的库 selectdatabase();

相关推荐

推荐阅读