AT4546 Grid 2
qiuweilin666
·
·
题解
本题本质是对 dp 思想的一种优化。
我们发现，这个组合数来源于将该棋盘视作一个杨辉三角，然后 dp 方案数，推出的结论满足斜杨辉三角。
那么我们恢复这个思想，由于不能用的点比较少，我们按不能用的点走。先将所有不能用的点按 x 为第一关键字，y 为第二关键字排序。
接下来我们设 dp_{i} 表示从原点到 i 点不经过其他不能用的点的方案数。其中枚举的所有 i 点都是不能用的点（或终点），以下给出原理：
其实我们可以设 dp_{i} 是所有点的方案数，但这样时空都承受不了。
但我们会发现，不能用的点是很少的，于是我们仅需讨论不能用的点即可。
因为讨论到任何一个点的方案数，都只需要这个点之前不能用的点的方案数。所以这样做是正确的。
对所有 i，dp_{i} 的初值应当都是原点到 i 的方案数（即
而为了不经过其他的障碍点，我们需要排除前面一些障碍点的方案。
对于每个 $i$，我们仅需枚举所有 $i$ 之前的 $j$，使 $x_{i} \ge x_{j}$ , $y_{i} \ge y_{j}$。
然后可以得出状态转移方程 $dp_{i}=dp_{i}-dp_{j} \times C^{x_{i}-x_{j}+y_{i}-y_{j}}_{x_{i}-x_{j}}$。
这里算出的就是同时至少经过 $i$，$j$ 两点的方案数。
至于会不会重叠，由于我们按 $x$，$y$ 排过序，再考虑原先的 $dp_{j}$ 都是只经过 $j$ 这一个障碍物的，所以不会有重叠。
最后贴个代码，线性筛阶乘逆元 $+$ 组合数 dp。
```cpp
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
#define mode 1000000007
#define maxn 200000
using namespace std;
ll inv[200005];
ll mul[200005];
void init()
{
inv[1]=1;
inv[0]=1;
mul[0]=1;
for(int i=2;i<=maxn;i++)
{
inv[i]=(mode-mode/i)*inv[mode%i]%mode;
}
for(int i=1;i<=maxn;i++)
{
inv[i]*=inv[i-1];
inv[i]%=mode;
mul[i]=mul[i-1]*i;
mul[i]%=mode;
}
}
int n,m,k;
struct Bad
{
int x,y;
}p[3005];
ll dp[3005];
bool cmp(Bad a,Bad b)
{
if(a.x==b.x)
{
return a.y<b.y;
}
return a.x<b.x;
}
ll C(int x,int y)
{
return mul[x]%mode*inv[y]%mode*inv[x-y]%mode;
}
int main()
{
// freopen("path.in","r",stdin);
// freopen("path.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
init();
for(int i=1;i<=k;i++)
{
scanf("%d%d",&p[i].x,&p[i].y);
}
k++;
p[k].x=n;
p[k].y=m;
sort(p+1,p+k+1,cmp);
for(int i=1;i<=k;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].x<=p[i].x&&p[j].y<=p[i].y)
{
dp[i]-=dp[j]*C(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%mode;
}
}
dp[i]=(dp[i]%mode+mode)%mode;
}
printf("%lld\n",dp[k]);
}
```