[JZOJ5411]【NOIP2017提高A组集训10.22】友谊_BAJim_H的博客-程序员资料

技术标签: 题解  ————其他dp  DP  

Description

Flowey 是一朵能够通过友谊颗粒传播LOVE 的小花.它的友谊颗粒分为两种,
圆粒的和皱粒的,它们依次排列组成了一个长度为2m 的序列.对于一个友谊颗
粒的序列,如果存在 1<=i<j<=2m ,满足以下条件:
1)i 为偶数,j 为奇数
2)第i 颗友谊颗粒和第j 颗友谊颗粒同为圆粒或同为皱粒
3)第i 颗友谊颗粒和第j 颗友谊颗粒都还没有被使用过
那么,就可以使用这两颗友谊颗粒,然后提升一次LV.
定义一个友谊颗粒的序列为高效的,当且仅当尽可能多的提升LV 后,序列
上剩余的友谊颗粒数量不超过2n。
现在,Flowey 想知道,长度为2m 的友谊颗粒序列,有多少个不同的序列是
高效的?
定义两个友谊颗粒序列是不同的,当且仅当存在1<=i<=2m,第i 颗友谊颗粒在
一个序列中为圆粒,而在另一个中为皱粒.
由于答案可能很大,你只需要求出答案对p 取模的结果.
对于60%的数据,满足n<=300,m<=300
对于100%的数据,满足1<=n<=3000,1<=m<=3000,2<=p<=1000000007

Solution

显然第一个和最后一个根本不能造成影响,直接去掉,n-1,m-1最后答案乘4
下面讨论都是去掉之后的

先考虑60%

设F[i][j][k]表示做到第i个点,偶数位上还剩j个圆粒,k个皱粒,直接转移即可。

统计答案时偶数位上的剩下的粒数小于n即可

考虑满分做法
可以将原序列看作一个二分图,偶数在上,奇数在下,每次做一列。

既然失配数不能超过N,那么我们在偶数列前面强行添加n个虚点,可圆可皱,不论排列,奇数点和它们匹配相当于失配。

那么现在DP时的失配已经和原来意义不同了,因为凭空多出n个虚点,无论怎么匹配,DP时的失配数始终是n,并且原本的失配数(前后两个失配不一样)一定不会超过n,因为前面的虚点最多只有n个

那么可以设 G[i][j] 表示做到第i列,偶数位上j个圆粒,那么剩下的皱粒个数就是 nj

添加的虚点实际上就是 G[i][0 ~ n]=1

下面来自某位巨犇LYD729的转化思想
由于其比较易懂,根据自己的理解又补充了一些,一起写在下面

或者说,设虚点的意义就是设了
G[i][j]=k=0njF[i][j][k]

但是这样会重复

对于某一个 F[i][x][y]

若存在 j>=x,nj>y
那么它至少在 G[i][j],G[i][j+1] 都算过

若在转移过程中,j始终大于0,那么一定会有至少一个x被算多了一次。

那么我们要求转移过程中j至少等于过0

于是我们增加一维 0/1 ,来表示其是否经历j=0

统计答案时只统计经历过的

Code

 #include <cstdio>
 #include <cstdlib>
 #include <algorithm>
 #include <cstring>
 #include <cmath>
 #include <iostream>
 #define fo(i,a,b) for(int i=a;i<=b;i++)
 #define fod(i,a,b) for(int i=a;i>=b;i--)
 #define N 3005
 #define LL long long
 using namespace std;
 int n,m;
 LL mo,f[N][N][2];
 int main()
 {
    cin>>n>>m>>mo;
    fo(i,0,n-1) f[0][i][i==0]=1;
    fo(i,1,m-1)
    {
        fo(j,0,n-1)
        {
            if(j==0) f[i][j][1]=((f[i-1][j][0]+f[i-1][j][1])*(LL)2+f[i-1][j+1][0]+f[i-1][j+1][1]+((j>0)?(f[i-1][j-1][0]+f[i-1][j-1][1]):0))%mo;
            else
            {
                f[i][j][1]=(f[i-1][j][1]*(LL)2+f[i-1][j+1][1]+((j>0)?f[i-1][j-1][1]:0))%mo;
                f[i][j][0]=(f[i-1][j][0]*(LL)2+f[i-1][j+1][0]+((j>0)?f[i-1][j-1][0]:0))%mo;
            }
        }
    }
    LL ans=0;
    fo(i,0,n-1) (ans+=f[m-1][i][1])%=mo;
    printf("%lld\n",ans*(LL)4%mo);
 }
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/hzj1054689699/article/details/78324131

智能推荐

geoserver集成geowebcache及leaflet加载geowebcache_简单GIS的博客-程序员资料_geoserver geowebcache

最近再弄geoserver的缓存,其实数据量并不大,但是本着能快一点是一点的想法,就弄了个geowebcache过程很简单,在web.xml添加存储位置即可{你的geoserver存储位置}\geoserver-2.15.0\webapps\geoserver\WEB-INF\web.xml中添加代码如下&lt;context-param&gt; &lt;par...

Java反射机制笔记_yinhuanxu的博客-程序员资料

很多时候,java程序运行中,我们需要在运行时了解类的信息,得到类的实例,并且进而继续得到类的方法,构造函数,权限,变量以及其他信息。这时候我们需要用到一门技术,java反射反射说白了,就是把我们的一些文件,一些字符串,一些地址上具体的配置信息,能够把他们动态的在运行期实例化,并且我们能够操作这些实例

【halcon】油污检测_阿卡基YUAN的博客-程序员资料

read_image (Image1, 'E:/work/OpenCV/Image/oil.jpg')decompose3(Image1, Image11, Image2, Image3)threshold (Image11, Regions, 85, 171)fill_up(Regions, RegionFillUp)connection(RegionFillUp, Conn...

Centos 7, Torque 单节点部署_weixin_30648587的博客-程序员资料

1.准备工作安装Torque必须首先配置linux主机名称,服务器主机名称大多默认localhost,不建议直接使用localhost。linux主机名称修改地址:http://www.cnblogs.com/smbin/p/8488909.htmllinux系统:Centos 7主机名称:master系统用户:rootTorque官网下载地址:http:...

spring data JPA_liweisnake的博客-程序员资料_"expressions.add(cb.equal(root.<integer> get(\"sho

最近使用了spring data jpa来完成数据访问层的实现。感觉比较强大,也比较复杂,中间还有不少限制。话说数据库sql的应用有点像打怪升级,一点一点不断增加难度。文章从4个层次讨论了jpa的用法,层层递进,希望能够帮到使用中的人

【Linux】Grub安装CentOS7_Beatfan_N的博客-程序员资料

        安装CentOS7主要需要镜像,从镜像中提取vmlinuz和initrd.img与iso文件放到fat32分区,对于大于4g的iso,只能放到ext2分区,使用windows的ext2工具可以将文件拷贝进去。        使用grub加载CentOS镜像时,需要加载kernel并设置iso文件所在盘,以及initrd。        建议使用grub的commandline进...

随便推点

Altium Designer 20 (1)——软件安装_青梅煮久的博客-程序员资料

一、稳压电源简介• 由 青梅煮久 写于 2021 年 05 月 27 日

.NET体系中的源程序安全问题_唐古拉山的博客-程序员资料

在.NET平台上,代码以中间语言的形式运行,它是.NET众多优势的基础。但在独立桌面应用中,它给源代码的安全带来了威胁。本文探讨产生这个问题的原因,分析可能的解决办法。   在Visual Studio.NET(VS.NET)体系中,VB、Visual C++以及C#之类的编译器把源程序编译成MSIL。MSIL即Microsoft Intermediate Language,或Microsof

pytho爬虫经常报错错误 Traceback (most recent call last) 错误信息_Am0o0s的博客-程序员资料

解读错误信息就可以定位错误。Traceback (most recent call last):这是错误的跟踪信息。File "XXX.py", line 13, in &lt;module&gt;f3('0')调用f3()出错了,错误出现在文件XXX.py的第13行代码,错误来源第9行:File “XXX.py”, line 12, in f3return f2(s)+1调用...

自己动手开发智能聊天机器人完全指南(附python完整源码)_数据饕餮的博客-程序员资料

一、前言人工智能时代,开发一款自己的智能问答机器人,一方面提升自己的AI能力,另一方面作为转型AI的实战练习。在此把学习过程记录下来,算是自己的笔记。二、正文2.1 下载pyaiml下载pyaiml2.2 安装pip install aiml安装aiml2.3 查看安装完成后,查看包信息,pip show查看aiml包信息三、源码3.1 智能机器人测试程序主程序3.2 配置文件配置文件3.3 AI

System V IPC vs POSIX IPC_guiwin的博客-程序员资料

TIP:What are the differences between System V IPC and POSIX IPC ? Why do we have two standards ? How to decide which IPC functions to use ?ANS:Both have the same basic tools -- semaphores, shar...

ACPI BIOS Error (bug): Failure creating named object_不可以不读书的博客-程序员资料

安装ubuntu时出现上诉问题当我们在为有独立显卡gpu的电脑安装Ubuntu系统时,有可能会遇到上述的问题。解决方法一:先把显示器接到集成显卡上,装完系统后,再接到独立显卡gpu,再为gpu配置驱动;解决方法二:当电脑没有集成显卡时,选择UEFI General ...disk进行安装,当安装过程进入到四个选项(try ubuntu, install ubuntu……),点击"e"进入edit mode,找到"quiet splash ---",把“---”换成“nomodeset”,然.

推荐文章

热门文章

相关标签