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

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个圆粒，那么剩下的皱粒个数就是 $n-j$

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

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

或者说，设虚点的意义就是设了
$G[i][j]=\sum\limits_{k=0}^{n-j}F[i][j][k]$

但是这样会重复

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

若存在 $j>=x,n-j>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);
 }

本文链接：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中添加代码如下<context-param> <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进...