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

题面

题解

先解决\(3216\)，求的是最小值为\(0\)。

因为起点就是\(0\)，所以就是在过程中不会到\(0\)以下。

那么两个相邻位置的合法走法可以转化成网格图上从\((0,0)\)走到\((n,m)\)，且不穿过直线\(y=x-b\)的方案数。

这个方案数显然可以组合数计算\(\displaystyle {n+m\choose n}-{n+m\choose n+b}\)。因为模数很蛋疼，所以\(exLucas\)一下就好了。其实也没有必要\(exLucas\)，因为模数分解后就是两个质数的乘积，所以直接\(Lucas\)后\(CRT\)合并就好了。

代码放最后面。

---

然后来解决\(3215\)，求的是极小值为\(0\)。

在路径上翻译一下的话就是只要往下走就必定走到\(0\)位置。

因为需要访问到当前点的时候，路径是在往下还是往上，所以来\(dp\)，设\(f[i][0/1]\)表示当前在\(i\)位置，是路径是在往上还是往下，分情况考虑转移。

• \(f[i][1]\rightarrow f[i+1][0]\)

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

• \(f[i][0]\rightarrow f[i+1][0]\)

  强行把\(i\)当做当前\(i\)节点的往上的路径的终点，那么又能确定两个\(0\)点，还是假设中间有\(2k\)个位置，这时候的答案是\(2^k\)。首先还是可以任意分组，但是第一次还可以选择是否从\(i\)继续向上延伸。

• \(f[i][1]\rightarrow f[i][1]\)

  首先左侧一定要走到底，那么还是可以确定两个\(0\)点。依旧分组，方案数是\(2^{k-1}\)，因为右侧需要从上面下来，所以强行把最后一段和右侧合并。

• \(f[i][0]\rightarrow f[i+1][1]\)

  还是强制先到\(0\)，还是中间是\(2k\)个位置，此时的贡献就是\(2^{k}\)。因为对于左侧考虑是否把第一段给合并进来，右侧强制把最后一段给合并进来，所以要考虑\(k\)个东西。

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

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

---

BZOJ3215代码

#include
    
     #include
     
      #include
      
       using namespace std;#define MOD 19940417#define MAX 1000100void 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
       
        >=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
    
     #include
     
      #include
      
       using namespace std;#define MOD 19940417#define MAX 1000100inline 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