一道计数类DP例题~~~

ps：P党似乎不多了……

我这只蒟蒻第一次写题解，而且计数类DP还是早上刚学的，现学现用，或者说是所谓的“浅谈”一番吧！况且这题写题解的人似乎并不多（大佬似乎不屑于光临此题）

进入正题

题目大意：扔给你一个h*w的棋盘，并给定n给不可以经过的格子的坐标，和（sang）蔼（xin）可（bing）亲（kuang）地让你计算从(1,1)开始走到(h,w)的合法路径的条数，答案对$10^9+7$取模。

看完题后，呵，简单，都做过过河卒这种题吧！递推在手，天下我有！！

大笑着，不经意间瞟了一下数据范围，笑容瞬间凝固……

$1<=h,w<=10^{5},1<=n<=2000 $

啥玩意？

无奈，出门左转，逃！

够英明的选择，但还有更英明的选择——学习！没错，学习！

好的，依阁下高见，我来学习了。

孺子可教，吭吭，听好了(冒犯)：

倘若你成了超人，通过了之前无法逾越的格子，那么你走到终点的路径总数是可以用一个组合数搞出来的。不会？那就对了，接着看。从起点走到终点，你必然走了$h-1$步往下，$w-1$步往右，对吧？总步数就是$h+w-2$ ,然后想想组合数，整条路径我走了$h-1$步往下，剩下$w-1$步就确定了。那么换种说法，我从$h+w-2$步中选$h-1$步往下，就可以确定唯一的一条路径，则总方案数为$C_{h+w-2}^{h-1}$种，同理，走$w-1$步往下，也可以确定唯一的一条路径，有$C_{h+w-2}^{w-1}$种方案数。两者等价。（等价？质疑请了解$C_n^m=C_n^{n-m}$）
但是，棋盘中有些点是不能走的，我们考虑用容斥原理去除多余方案。

\[Ans=C_{h+w-2}^{h-1}-P_1+P_2-P_3+...+(-1)^n*P_n
\]

其中$P_i$表示经过i个不能走的点的路径，但是，此题n<=2000，容斥原理直接炸掉。（况且我也不会容斥原理，我太弱了）

但我们不急，不慌，不乱。想想DP，乱设一下，设$f_i$表示从(1,1)走到第i个不能走的点，且不经过其它不能走的点的方案数。推一下，设$x_i,y_i$为第i个不能通过的点（以$x_i$为第一关键字，$y_i$为第二关键字排好序后），我们可以用上文推到的东西先算出(1,1)这个点到总方案数，然后依照我们的定义：“不能经过其他无法通过的点”，所以要减去前$i-1$个点到此点的方案数（不合定义），就是$f_i$了,综上：
\[f_i=C_{x_i+y_i-2}^{x_i-1}-\sum_{j=1}^{i-1}f_j·C_{x_i+y_i-x_j-x_j}^{x_i-x_j}
\]
我们可以让终点成为不可通过的点，答案就是$f_{n+1}$了。
嗯嗯，讲完了。

$O(n^2)$ 的时间复杂度，完美AC。$n<=2000$

那么，再综合解题步骤：

以$x_i$为第一关键字，$y_i$为第二关键字排好序。
提前预处理出组合数所需要的逆元（逆元可以自学，复习时我可能会写来巩固一下）。
把终点加入$f$中，计算$f_i$的值，答案就是$f_{n+1}$

附上完整代码，放心食用。(pascal的，重点在思路，语言无太大关系)

const p=trunc(1e9)+7;

type

        node=record

                x,y:int64;

        end;

var

        fac,inv:array [0..200005] of int64;

        f:array [0..3005] of int64;

        a,c:array [0..3005] of node;

        n,m,i,j,k,maxn:longint;

procedure msort(l,r:longint);

var

        i,j,k,mid:longint;

begin

        mid:=(l+r)>>1;

        if (l<mid) then msort(l,mid);

        if (mid+1<r) then msort(mid+1,r);

        i:=l;

        j:=mid+1;

        k:=l;

        while (i<=mid)and(j<=r) do

        begin

                if (a[i].x<a[j].x)or(a[i].x=a[j].x)and(a[i].y<a[j].y) then

                begin

                        c[k]:=a[i];

                        inc(i);

                        inc(k);

                end

                else begin

                        c[k]:=a[j];

                        inc(j);

                        inc(k);

                end;

        end;

        while (i<=mid) do

        begin

                c[k]:=a[i];

                inc(i);

                inc(k);

        end;

        while (j<=r) do

        begin

                c[k]:=a[j];

                inc(j);

                inc(k);

        end;

        for i:=l to r do a[i]:=c[i];

end;

function qpow(x,y:int64):int64;

var

        res:int64;

begin

        res:=1;

        while (y>0) do

        begin

                if (y and 1=1) then res:=res*x mod p;

                x:=x*x mod p;

                y:=y>>1;

        end;

        exit(res);

end;

procedure prepare;

var

        i:longint;

begin

        fac[0]:=1;

        for i:=1 to maxn do fac[i]:=fac[i-1]*i mod p;

        inv[maxn]:=qpow(fac[maxn],p-2);

        for i:=maxn-1 downto 0 do inv[i]:=inv[i+1]*(i+1) mod p;

end;

function combination(n,m:int64):int64;

begin

        if (n<m) then exit(0);

        exit(fac[n]*inv[n-m] mod p*inv[m] mod p);

end;

begin

        //assign(input,'path.in');reset(input);

        //assign(output,'path.out');rewrite(output);

        readln(n,m,k);

        if (n<m) then maxn:=m<<1

        else maxn:=n<<1;

        for i:=1 to k do read(a[i].x,a[i].y);

        k:=k+1;

        a[k].x:=n;a[k].y:=m;

        msort(1,k);

        prepare;

        for i:=1 to k do

        begin

                f[i]:=combination(a[i].x+a[i].y-2,a[i].x-1);

                for j:=1 to i-1 do

                        f[i]:=(f[i]-f[j]*combination(a[i].x+a[i].y-a[j].x-a[j].y,a[i].x-a[j].x) mod p+p) mod p;

        end;

        write(f[k]);

        //close(input);close(output);

end.

曲终，继续努力，备战CSP2019。

时隔两年，因某些原因补上 $\text{C++}$ 代码

#include <cstdio>

#include <algorithm>

#define RE register

#define IN inline

#define LL long long

using namespace std;

const int N = 2e5 + 5, P = 1e9 + 7;

int n, m, k, maxn;

LL fac[N], inv[N], f[2005];

struct node{int x, y;}a[2005];

IN bool cmp(node a, node b){return (a.x < b.x ? 1 : (a.x == b.x ? a.y < b.y: 0));}

IN int fpow(LL x, int y){LL s = 1; for(; y; y >>= 1, x = x * x % P) if (y & 1) s = s * x % P; return s;}

IN int C(int n, int m){if (n < m) return 0; return fac[n] * inv[n - m] % P * inv[m] % P;}

int main()

{

	scanf("%d%d%d", &n, &m, &k), maxn = max(n, m) << 1;

	for(RE int i = 1; i <= k; i++) scanf("%d%d", &a[i].x, &a[i].y);

	a[++k] = node{n, m}, sort(a + 1, a + k + 1, cmp), fac[0] = inv[0] = 1;

	for(RE int i = 1; i <= maxn; i++) fac[i] = fac[i - 1] * i % P;

	inv[maxn] = fpow(fac[maxn], P - 2);

	for(RE int i = maxn - 1; i; i--) inv[i] = inv[i + 1] * (i + 1) % P;

	for(RE int i = 1; i <= k; i++)

	{

		f[i] = C(a[i].x + a[i].y - 2, a[i].x - 1);

		for(RE int j = 1; j < i; j++)

			f[i] = (f[i] - f[j] * C(a[i].x + a[i].y - a[j].x - a[j].y, a[i].x - a[j].x) % P + P) % P;

	}

	printf("%lld\n", f[k]);

}

巴特西

【Gerald and Giant Chess】

一道计数类DP例题~~~

进入正题

孺子可教，吭吭，听好了(冒犯)：

最新文章

热门文章