点击刷新
题意：给出一个矩阵棋盘，大小不超过10^5。上面有n个非法点(n<=2000)不可以踩，从左上角开始走到右下角，每次只能向下或者向右移动。问有多少种走法。结果对10^9+7取模。
分析：
组合数学DP
设dp[i]表示从左上角开始不经过非法点走到第i个非法点有多少种方法。
dp[i]=num(s, point[i]) - sigma( dp[j] * num(point[j], point[i]) );
其中，sigma表示加和，s是起始点，j遍历所有在点i左上方的点。num(a,b)表示从a到b有多少种走法（不用避开非法点）。
num可以直接用组合数表示，即c(x+y-2, x -1)。
这道题涉及到了较大的组合数取模问题。求大组合数方法如下：
可以先处理出所有1～n的阶乘，存入数组。factorial[i]表示i的阶乘取模后的结果。
并求出所有的阶乘在该模运算下的逆元，存入数组。inverse[i]表示factorial[i]的逆元。
c(n,m)原本等于( n! / (n-m)! ) / m!，现在用这两个数组可以表示为factorial[n] * inverse[n-m] * inverse[m]。
模板如下：
#define LL long long const int MAX_M = (int)(2e5) + 20; const int MOD = (int)(1e9) + 7; LL multi_mod(LL a, LL b, LL c) { //返回(a*b) mod c,a,b,c<2^63 a %= c; b %= c; LL ret = 0; while (b) { if (b & 1) ret = (ret + a) % c; a <<= 1; a %= c; b >>= 1; } return ret; } LL pow_mod(LL x, LL n, LL mod) { //返回x^n mod c ,非递归版 x %= mod; if (n == 1) return x; LL ret = 1; while (n) { if (n & 1) ret = multi_mod(ret, x, mod); n >>= 1; x = multi_mod(x, x, mod); } return ret; } long long get_inverse(long long a) { return pow_mod(a, MOD - 2, MOD); } long long factorial[MAX_M]; long long inverse[MAX_M]; void init_comb(int n) { factorial[0] = 1; for (int i = 1; i <= n; i++) { factorial[i] = factorial[i - 1] * i; factorial[i] %= MOD; } inverse[n] = get_inverse(factorial[n]); for (int i = n - 1; i >= 0; i--) { inverse[i] = inverse[i + 1] * (i + 1); inverse[i] %= MOD; } } long long comb(long long a, long long b) { long long ret = factorial[a] * inverse[a - b]; ret %= MOD; ret *= inverse[b]; ret %= MOD; return ret; }
求逆元可以使用扩展欧几里德算法，但是比较麻烦。这次我使用了一个更为简单的算法，费马小定理。
即：当p是质数且a和p互质，那么a^(p-1)=1 (mod p)
而逆元的定义是x * y=1 (mod p)则y是x的逆元。令x=a，且a与p互质，则由a^(p-1)=1 (mod p)可得：y=a^(p-2)。
对于求a的逆元这个问题，a<p且p是质数，自然可以利用上面的结论，a的逆元就是a^(p-2)。
求逆元模板如下：
LL multi_mod(LL a, LL b, LL c) { //返回(a*b) mod c,a,b,c<2^63 a %= c; b %= c; LL ret = 0; while (b) { if (b & 1) ret = (ret + a) % c; a <<= 1; a %= c; b >>= 1; } return ret; } LL pow_mod(LL x, LL n, LL mod) { //返回x^n mod c ,非递归版 x %= mod; if (n == 1) return x; LL ret = 1; while (n) { if (n & 1) ret = multi_mod(ret, x, mod); n >>= 1; x = multi_mod(x, x, mod); } return ret; } long long get_inverse(long long a) { return pow_mod(a, MOD - 2, MOD); }
本题代码如下：
#include <cstdio> #include <algorithm> using namespace std; #define d(x) #define LL long long const int MAX_N = 2020; const int MAX_M = (int)(2e5) + 20; const int MOD = (int)(1e9) + 7; int row_num, col_num; int n; pair<int, int> point[MAX_N]; long long dp[MAX_N]; void input() { scanf("%d%d%d", &row_num, &col_num, &n); for (int i = 0; i < n; i++) { int a, b; scanf("%d%d", &a, &b); point[i] = make_pair(a, b); } point[n++] = make_pair(row_num, col_num); point[n++] = make_pair(1, 1); for (int i = 0; i < n; i++) { point[i].first--; point[i].second--; } } LL multi_mod(LL a, LL b, LL c) { //返回(a*b) mod c,a,b,c<2^63 a %= c; b %= c; LL ret = 0; while (b) { if (b & 1) ret = (ret + a) % c; a <<= 1; a %= c; b >>= 1; } return ret; } LL pow_mod(LL x, LL n, LL mod) { //返回x^n mod c ,非递归版 x %= mod; if (n == 1) return x; LL ret = 1; while (n) { if (n & 1) ret = multi_mod(ret, x, mod); n >>= 1; x = multi_mod(x, x, mod); } return ret; } long long get_inverse(long long a) { return pow_mod(a, MOD - 2, MOD); } long long factorial[MAX_M]; long long inverse[MAX_M]; void init_comb(int n) { factorial[0] = 1; for (int i = 1; i <= n; i++) { factorial[i] = factorial[i - 1] * i; factorial[i] %= MOD; } inverse[n] = get_inverse(factorial[n]); for (int i = n - 1; i >= 0; i--) { inverse[i] = inverse[i + 1] * (i + 1); inverse[i] %= MOD; } } long long comb(long long a, long long b) { long long ret = factorial[a] * inverse[a - b]; ret %= MOD; ret *= inverse[b]; ret %= MOD; return ret; } int main() { init_comb(200000); input(); sort(point, point + n); dp[0] = 1; for (int i = 1; i < n; i++) { dp[i] = comb(point[i].first + point[i].second, point[i].second); for (int j = 1; j < i; j++) { if (point[j].first <= point[i].first && point[j].second <= point[i].second) { long long a = point[i].first - point[j].first; a += point[i].second - point[j].second; long long b = point[i].second - point[j].second; dp[i] -= (dp[j] * comb(a, b)) % MOD; dp[i] += MOD; dp[i] %= MOD; } } d(printf("dp[%d] = %d\n", i, (int)dp[i])); } printf("%d\n", (int)dp[n - 1]); return 0; }
© 著作权归作者所有
举报
发表评论
0/200
