【BZOJ3215/3216】[ZJOI2013]话旧/话旧2（组合数学，动态规划）

题面

题解

先解决(3216)，求的是最小值为(0)。
因为起点就是(0)，所以就是在过程中不会到(0)以下。
那么两个相邻位置的合法走法可以转化成网格图上从((0,0))走到((n,m))，且不穿过直线(y=x-b)的方案数。
这个方案数显然可以组合数计算(displaystyle {n+mchoose n}-{n+mchoose n+b})。因为模数很蛋疼，所以(exLucas)一下就好了。其实也没有必要(exLucas)，因为模数分解后就是两个质数的乘积，所以直接(Lucas)后(CRT)合并就好了。
代码放最后面。

然后来解决(3215)，求的是极小值为(0)。
在路径上翻译一下的话就是只要往下走就必定走到(0)位置。
因为需要访问到当前点的时候，路径是在往下还是往上，所以来(dp)，设(f[i][0/1])表示当前在(i)位置，是路径是在往上还是往下，分情况考虑转移。

(f[i][1] ightarrow f[i+1][0])

先考虑最简单的一种情况，即当前点的路径还在往下，而要用一条往上的路径穿过(i+1)。那么延长这两条路径，能够确定两个(0)点，剩下的就是在这两个零点之间反复横跳，设这两个零点之间的距离为(2k)，那么要进行(k)次向上(k)次向下，而分组后两者的分组必定两两相等，所以就是把(k)分成任意数量组的方案数，这个答案是(2^{k-1})。即对于(i)考虑，其要么和(i-1)在一组要么不在。

(f[i][0] ightarrow f[i+1][0])
强行把(i)当做当前(i)节点的往上的路径的终点，那么又能确定两个(0)点，还是假设中间有(2k)个位置，这时候的答案是(2^k)。首先还是可以任意分组，但是第一次还可以选择是否从(i)继续向上延伸。
(f[i][1] ightarrow f[i][1])
首先左侧一定要走到底，那么还是可以确定两个(0)点。依旧分组，方案数是(2^{k-1})，因为右侧需要从上面下来，所以强行把最后一段和右侧合并。
(f[i][0] ightarrow f[i+1][1])
还是强制先到(0)，还是中间是(2k)个位置，此时的贡献就是(2^{k})。因为对于左侧考虑是否把第一段给合并进来，右侧强制把最后一段给合并进来，所以要考虑(k)个东西。

那么直接(dp)就完了，最大值随便求求就好了。

注意这里有些特殊情况，导致(kle 0)，把这些情况特判处理就好了。

BZOJ3215代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 19940417
#define MAX 1000100
void add(int &x,int y){x=(x+y)%MOD;}
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int fpow(int a,int b)
{
	int s=1;
	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}
	return s;
}
struct Data{int x,y;}a[MAX];
bool operator<(Data a,Data b){return a.x<b.x;}
bool operator==(Data a,Data b){return a.x==b.x&&a.y==b.y;}
int n,K,mx;
int f[MAX][2];
int main()
{
	n=read();K=read();
	for(int i=1;i<=K;++i)a[i].x=read(),a[i].y=read();
	a[++K]=(Data){0,0};a[++K]=(Data){n,0};
	sort(&a[1],&a[K+1]);K=unique(&a[1],&a[K+1])-a-1;
	f[1][1]=1;
	for(int i=1;i<K;++i)
	{
		int p=a[i+1].x-a[i].x-a[i+1].y-a[i].y;p>>=1;
		mx=max(mx,(a[i+1].x+a[i+1].y-a[i].x+a[i].y)/2);
		if(a[i+1].y-a[i].y==a[i].x-a[i+1].x)add(f[i+1][1],(f[i][0]+f[i][1])%MOD);
		else if(a[i+1].y-a[i].y==a[i+1].x-a[i].x)add(f[i+1][0],(f[i][0]+(a[i].y?0:f[i][1]))%MOD);
		else if(p<0)add(f[i+1][1],f[i][0]);
		else if(p==0)add(f[i+1][0],(f[i][0]+f[i][1])%MOD),add(f[i+1][1],f[i][0]);
		else
		{
			int d=fpow(2,p-1);
			if(a[i+1].y)add(f[i+1][0],(f[i][1]+2ll*f[i][0])*d%MOD);
			add(f[i+1][1],(f[i][1]+2ll*f[i][0])*d%MOD);
		}
	}
	printf("%d %d",f[K][1],mx);
	return 0;
}

BZOJ3216代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 19940417
#define MAX 1000100
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
struct Data{int x,y;}a[MAX];
bool operator<(Data a,Data b){return a.x<b.x;}
int fac[3]={0,7,2848631};
int jc[3][2848631];
int inv[3][2848631];
void exgcd(int a,int b,int &x,int &y){if(!b){x=1,y=0;return;}exgcd(b,a%b,y,x);y-=a/b*x;}
int Inv(int n,int m){int x,y;exgcd(n,m,x,y);return (x%m+m)%m;}
int C(int n,int m,int p)
{
	if(n<m)return 0;
	return 1ll*jc[p][n]*inv[p][m]%fac[p]*inv[p][n-m]%fac[p];
}
int Lucas(int n,int m,int p)
{
	if(n<p)return C(n,m,p);
	return 1ll*Lucas(n/fac[p],m/fac[p],p)*C(n%fac[p],m%fac[p],p)%fac[p];
}
int C(int n,int m)
{
	int w[3]={0,0,0};if(n<m||n<0||m<0)return 0;
	for(int i=1;i<=2;++i)w[i]=Lucas(n,m,i);
	int x=Inv(fac[1],fac[2]);
	x=1ll*x*(w[2]-w[1]+MOD)%MOD;
	return (1ll*x*fac[1]+w[1])%MOD;
}
int Calc(int n,int m,int b)
{
	int ret=C(n+m,n)-C(n+m,n+b);
	return (ret+MOD)%MOD;
}
int n,K,ans=1,mx;
int main()
{
	n=read();K=read();
	for(int i=1;i<=K;++i)a[i].x=read(),a[i].y=read();
	a[++K]=(Data){0,0};a[++K]=(Data){n,0};
	sort(&a[1],&a[K+1]);
	for(int i=1;i<=2;++i)
	{
		jc[i][0]=inv[i][0]=inv[i][1]=1;
		for(int j=1;j<fac[i];++j)jc[i][j]=1ll*jc[i][j-1]*j%fac[i];
		for(int j=2;j<fac[i];++j)inv[i][j]=1ll*inv[i][fac[i]%j]*(fac[i]-fac[i]/j)%fac[i];
		for(int j=2;j<fac[i];++j)inv[i][j]=1ll*inv[i][j-1]*inv[i][j]%fac[i];
	}
	for(int i=1;i<K;++i)
	{
		int b=a[i].y+1;
		int n=a[i+1].x-a[i].x;
		if(!n)continue;
		int m=a[i+1].y-a[i].y;
		int up=(n+m)/2,dn=(n-m)/2;
		ans=1ll*ans*Calc(up,dn,b)%MOD;
		mx=max(mx,a[i].y+up);
	}
	printf("%d %d
",ans,mx);
	return 0;
}