[JZOJ5411]【NOIP2017提高A组集训10.22】友谊

[JZOJ5411]【NOIP2017提高A组集训10.22】友谊

Description

Flowey 是一朵能够通过友谊颗粒传播LOVE 的小花．它的友谊颗粒分为两种，
圆粒的和皱粒的，它们依次排列组成了一个长度为2m 的序列．对于一个友谊颗
粒的序列，如果存在 1<=i<j<=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] $G[i][j]$表示做到第i列，偶数位上j个圆粒，那么剩下的皱粒个数就是 n−j $n-j$

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

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

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

但是这样会重复

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

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

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

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

于是我们增加一维 0/1 $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 longusing 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("%lldn",ans*(LL)4%mo);}