Problem题目简述
恶梦是一个登山爱好者,今天他来到了黄山。 俗话说的好,不走回头路。所以在黄山,你只能往前走,或者往上走。并且很显然的是,当你走到山脊的时候,你不能够往上走,你只能往前走一步再往上走。 抽象一点而言就是,你可以把黄山视为一个 N * N 格点图,恶梦从(0,0)开始出发,要走到(N,N)。当他走到位置(x,y)的时候,它可以往(x + 1,y),或(x,y+1)走。并且当他走到(x,x)的时候,由于他已经处在了山脊上,所以他不能够往(x,x+1)方向上走。 当恶梦兴致勃勃准备开始爬山的时候,他的同伴告诉他,黄山由于年久失修,有一些位置出现了大坑,不能走。恶梦觉得更刺激了,但他想先知道他能有多少种方式走到黄山顶。 由于这个数字很大,所以你只需要将答案对 10^9 + 7 取模输出即可。
输入格式
第一行包括两个整数 N,C,分别表示你可以把黄山视作一个 N * N 的格点图,并且黄山上面有 C 个 位置出现了大坑。 接下来的 C 行,每行包括两个整数 X,Y,表示 X,Y 这个位置不能走。保证 X>=Y,也就是说(X,Y)必然在山上。 保证这 C 个点互不相同。
输出格式
输出只有一个整数 Ans,表示恶梦爬上山顶的路径数对 取模的值。
样例输入输出
walk.in 7 4 6 5 5 3 2 1 7 1 walk.out 34
数据范围
对于 30%的数据,保证 N<=5000 对于另外 20%的数据,保证 C=0 对于另外 20%的数据,保证 C=1 对于 100%的数据,保证 N<=100000,C<=1000 保证对于(0,0),(N,N)不存在障碍点。
Solution
前排Orz跪神犇 来自Philips Weng的题解 我才不会告诉你密码gydg （！有智商！）
Code;typedef pair<int,int> P;const int MAXM = 1005,MAXN = 200015,Mo = int(1e9) + 7;P Block[MAXM];int Fc[MAXN],Rv[MAXN],F[MAXN],N,C;int Quick(int a,int b){if (!b) return 1;int mid = Quick(a,b >> 1);if (b & 1) return mid * 1ll * mid % Mo * a % Mo;return mid * 1ll * mid % Mo;}int Getc(int n,int m){if (m > n) return 0;return Fc[n] * 1ll * Rv[m] % Mo * Rv[n – m] % Mo;}int Normal(int s,int t,int x,int y){if (x < s || y < t) return 0;return Getc(x + y – s – t,x – s);}int Walk(int s,int t,int x,int y){return (Normal(s,t,x,y) – Normal(s,t,y – 1,x + 1) + Mo) % Mo;}int main(){freopen(“walk.in”,”r”,stdin),freopen(“walk.out”,”w”,stdout);scanf(“%d%d”, &N, &C);Fc[0] = 1;for(int i = 1;i <= N * 2 + 5;i ++) Fc[i] = Fc[i – 1] * 1ll * i % Mo;Rv[N * 2 + 5] = Quick(Fc[N * 2 + 5], Mo – 2);for(int i = N * 2 + 5;i;i –) Rv[i – 1] = Rv[i] * 1ll * i % Mo;for(int i = 1;i <= C;i ++) scanf(“%d%d”, &Block[i].fe, &Block[i].se);Block[++ C] = P(N,N);sort(Block + 1,Block + C + 1);for(int i = 1;i <= C;i ++){F[i] = Walk(0,0,Block[i].fe,Block[i].se);for(int j = 1;j < i;j ++)if (Block[j].se <= Block[i].se)F[i] = (F[i] – F[j] * 1ll * Walk(Block[j].fe,Block[j].se,Block[i].fe,Block[i].se) % Mo + Mo) % Mo;}printf(“%d\n”, F[C]);return 0;}End.
，一个背包，几本书，所有喜欢的歌，
