2 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5+10; const LL mod=1e9+7; LL dp[3100],fac[2*N],finv[2*N]; //dp[i]表示(1,1)到达第i个障碍点的方案数（不经过其他障碍点） struct node{int x,y;}p[3100]; inline LL ksm(LL a,LL b) { LL res=1ll; for(;b;(a*=a)%=mod,b>>=1)if(b&1)(res*=a)%=mod; return res; } inline LL C(int n,int m)//n个选m个 { return fac[n]*finv[m]%mod *finv[n-m]%mod; } signed main() { int n,h,w;scanf("%d%d%d",&h,&w,&n); for(int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),p[i]={x,y}; sort(p+1,p+n+1,[](const node &a,const node &b){return a.x<b.x || (a.x==b.x && a.y<b.y);}); p[n+1]={h,w}; fac[0]=finv[0]=1; for(int i=1;i<=h+w;i++) { fac[i]=(fac[i-1]*i)%mod; finv[i]=ksm(fac[i],mod-2); } for(int i=1;i<=n+1;i++) { dp[i]=C(p[i].x+p[i].y-2,p[i].x-1); for(int j=1;j<i;j++) { if(p[j].y>p[i].y)continue; int XL=p[i].x-p[j].x,YL=p[i].y-p[j].y; dp[i]=((dp[i]-dp[j]*C(XL+YL,XL)%mod)%mod+mod)%mod; } } printf("%lld\n",dp[n+1]); return 0; }在一张无障碍的地图中，从 ((1, 1)) 走到 ((i, j)) 的方案数为：
至于原因，是可以把一条路径的走法理解为：从 (i + j - 2) 次移动中选择 (i - 1) 次向下，其他的向右，而按这样选择的走法就一定能到达点 ((i, j))。
那如果地图中有一个障碍呢？
这样就不好用组合数直接统计了，实际上在这种情况下，直接正方向的计算并不轻松，那正难则反，我们就考虑如何把所有路径中，经过了障碍的给去掉。
于是我们来计算所有经过了障碍的路径：
设障碍的位置为 ((x, y))，则经过障碍的方案数为：
- 从 ((1, 1)) 到 ((x, y)) 的方案数与从 ((x, y)) 到 ((h, w)) 的方案数之积。
一个障碍的方案数计算出来了，那再加一个障碍呢？再加 (n) 个障碍呢？
一种暴力的方法就是，把每个经过一个障碍的路径从总方案数里去掉，在把所有经过两个障碍的路径加回来，再把三条的删去，……诸如此类，用容斥的思想把答案计算出来。但这样的复杂度实在不能接受，故我们要考虑一种不会算重的计数方法，以省略掉复杂度极高的枚举和容斥。
于是我们可以定义 (dp(i)) 代表从 ((1, 1)) 到第 (i) 个障碍 ((x_i, y_i))，中间不经过其他障碍的方案数。当然，我们可以令 ((h, w)) 为第 (n+1) 个障碍，那么答案就是 (dp(n+1))。
我们发现，可以合理的利用以前计算过的方案数不重不漏地推出当前的状态，即：
$$dp(i) = \binom{x_i + y_i - 2}{x_i - 1} - \sum_{j=1}^{i-1} dp(j) \times \binom{x_i - x_j + y_i - y_j}{x_i - x_j}$$看起来这个似乎像把经过一个障碍的方案数扣掉了，就不管了？那为什么是对的呢？
实际上，这个和扣掉一个点的方法并不一样，因为 (dp(i)) 记录的是不经过任何障碍的方案数。
故上面的转移方程中，(\sum_{j=1}^{i-1} dp(j) \times \binom{x_i - x_j + y_i - y_j}{x_i - x_j}) 所去除掉的路径都一定是不重不漏的，因为任意一个 (j) 对应的都是第一次经过障碍 (j) 的方案数，而和式中任意一个小于 (j) 的 (k)，(k) 在和式中去掉的路径第一次经过的障碍都不是 (j)，所以一定没有被多次去除掉的路径，这就是对于上述转移方程的正确性证明。那么我们只要预处理出阶乘及其逆元，从而 (O(1)) 的计算组合数即可。
因为计算某一个 (i) 的方案数所用的时间是 (O(n)) 级别的，所以总复杂度是 (O(n^2)) 的。
-
0
huangzheng
LV 6
@ 2025-10-8 17:00:09
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5+10; const LL mod=1e9+7; LL dp[3100],fac[2*N],finv[2*N]; //dp[i]表示(1,1)到达第i个障碍点的方案数（不经过其他障碍点） struct node{int x,y;}p[3100]; inline LL ksm(LL a,LL b) { LL res=1ll; for(;b;(a*=a)%=mod,b>>=1)if(b&1)(res*=a)%=mod; return res; } inline LL C(int n,int m)//n个选m个 { return fac[n]*finv[m]%mod *finv[n-m]%mod; } signed main() { int n,h,w;scanf("%d%d%d",&h,&w,&n); for(int i=1,x,y;i<=n;i++) scanf("%d%d",&x,&y),p[i]={x,y}; sort(p+1,p+n+1,[](const node &a,const node &b){return a.x<b.x || (a.x==b.x && a.y<b.y);}); p[n+1]={h,w}; fac[0]=finv[0]=1; for(int i=1;i<=h+w;i++) { fac[i]=(fac[i-1]*i)%mod; finv[i]=ksm(fac[i],mod-2); } for(int i=1;i<=n+1;i++) { dp[i]=C(p[i].x+p[i].y-2,p[i].x-1); for(int j=1;j<i;j++) { if(p[j].y>p[i].y)continue; int XL=p[i].x-p[j].x,YL=p[i].y-p[j].y; dp[i]=((dp[i]-dp[j]*C(XL+YL,XL)%mod)%mod+mod)%mod; } } printf("%lld\n",dp[n+1]); return 0; }
在一张无障碍的地图中，从 \((1, 1)\) 走到 \((i, j)\) 的方案数为：至于原因，是可以把一条路径的走法理解为：从 (i + j - 2) 次移动中选择 (i - 1) 次向下，其他的向右，而按这样选择的走法就一定能到达点 ((i, j))。
那如果地图中有一个障碍呢？
这样就不好用组合数直接统计了，实际上在这种情况下，直接正方向的计算并不轻松，那正难则反，我们就考虑如何把所有路径中，经过了障碍的给去掉。
于是我们来计算所有经过了障碍的路径：
设障碍的位置为 ((x, y))，则经过障碍的方案数为：
- 从 ((1, 1)) 到 ((x, y)) 的方案数与从 ((x, y)) 到 ((h, w)) 的方案数之积。
一个障碍的方案数计算出来了，那再加一个障碍呢？再加 (n) 个障碍呢？
一种暴力的方法就是，把每个经过一个障碍的路径从总方案数里去掉，在把所有经过两个障碍的路径加回来，再把三条的删去，……诸如此类，用容斥的思想把答案计算出来。但这样的复杂度实在不能接受，故我们要考虑一种不会算重的计数方法，以省略掉复杂度极高的枚举和容斥。
于是我们可以定义 (dp(i)) 代表从 ((1, 1)) 到第 (i) 个障碍 ((x_i, y_i))，中间不经过其他障碍的方案数。当然，我们可以令 ((h, w)) 为第 (n+1) 个障碍，那么答案就是 (dp(n+1))。
我们发现，可以合理的利用以前计算过的方案数不重不漏地推出当前的状态，即：
$dp(i) = \binom{x_i + y_i - 2}{x_i - 1} - \sum_{j=1}^{i-1} dp(j) \times \binom{x_i - x_j + y_i - y_j}{x_i - x_j}$
看起来这个似乎像把经过一个障碍的方案数扣掉了，就不管了？那为什么是对的呢？
实际上，这个和扣掉一个点的方法并不一样，因为 (dp(i)) 记录的是不经过任何障碍的方案数。
故上面的转移方程中，(\sum_{j=1}^{i-1} dp(j) \times \binom{x_i - x_j + y_i - y_j}{x_i - x_j}) 所去除掉的路径都一定是不重不漏的，因为任意一个 (j) 对应的都是第一次经过障碍 (j) 的方案数，而和式中任意一个小于 (j) 的 (k)，(k) 在和式中去掉的路径第一次经过的障碍都不是 (j)，所以一定没有被多次去除掉的路径，这就是对于上述转移方程的正确性证明。那么我们只要预处理出阶乘及其逆元，从而 (O(1)) 的计算组合数即可。
因为计算某一个 (i) 的方案数所用的时间是 (O(n)) 级别的，所以总复杂度是 (O(n^2)) 的。
- 1
