CSP赛前集训 【路径】

路径

题目描述：（暂不提供）

这道题很明显是一道原题。 原题： Gerald and Giant Chess

然后直接那么做就好了 （逃

这题其实之前也没做过。但赛后听说是原题结果发现果真是原题。。。

首先$N$和$M$都很大，而$K$比较小，那么我们的状态肯定与$K$有关。

首先将那$K$个点按照横纵坐标从小到大排序。

设$f_i$表示到第$i$个点，且途中不经过任何一个被淹点的方案数。

首先考虑走到当前这个被淹点的方案数，也就是$C_{x_i+y_i}^{x_i}$ 因为方案就是杨辉三角，当然就是这样了。

考虑中间有很多重复的点，也就是当$x_j<=x_i$且$y_j<=y_i$是要减去$j$的贡献。

也就是减去$f_j\ast C_{x_i-x_j+y_i-y_j}^{x_i-x_{}j}$。

早上睡得迷迷糊糊。然后打的时候快速幂打错了调了好久。

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 3010; const int M = 200010; const int mod = 1000000007; inline void read(int &x) { char ch = getchar(); x = 0; for(;ch < '0' || ch > '9';) ch = getchar(); for(;ch >= '0' && ch <= '9';) x = x * 10 + (ch ^ '0'), ch = getchar(); } struct node{ int x,y; } a[N]; int n,m,k,cnt = 0; ll f[N],fac[M] = {1},inv[M] = {1}; bool cmp(node a,node b) { return a.x < b.x || (a.x == b.x && a.y < b.y); } inline int f_pow(int a,int x) { int ret = 1; for(;x;x >>= 1) (x & 1) && (ret = 1ll * ret * a % mod), a = (1ll * a * a) % mod; return ret; } inline ll C(int x,int y) { return 1ll * fac[y] * inv[y - x] % mod * inv[x] % mod; } int main() { freopen("path.in","r",stdin); freopen("path.out","w",stdout); read(n), read(m), read(k); a[cnt] = (node){ 0,0 }; for(int i = 1;i <= k; ++ i) ++cnt, read(a[cnt].x), read(a[cnt].y); a[++cnt] = (node){ n,m }; sort(a + 1,a + 1 + cnt,cmp); for(int i = 1;i < M; ++ i) fac[i] = 1ll * fac[i - 1] * i % mod, inv[i] = 1ll * f_pow(fac[i],mod - 2) % mod; for(int i = 1;i <= cnt; ++ i) { f[i] = C(a[i].x,a[i].x + a[i].y) % mod; for(int j = 1;j < i; ++ j) if(a[i].x >= a[j].x && a[i].y >= a[j].y) f[i] = (f[i] - 1ll * (1ll * f[j] * C(a[i].x - a[j].x,a[i].x + a[i].y - a[j].x - a[j].y) % mod) + mod) % mod; } printf("%lld",(f[cnt] + mod) % mod); fclose(stdin); fclose(stdout); return 0; }

对了，考场数组差点点开小了。算组合数的时候那个底数是$2N$啊。 调了好久就没时间写$T1$了。