题目大意
有一个$n\times m$的矩阵,有一些点不能经过,现在从第一行开始每一行选一个点,下一行选的点必须比上一行靠右,问不经过障碍点的方案数。
题目吐槽
暴力膜蛤不可取,膜蛤不当必被续。
题目分析
首先对于这一类取模的题目,一般有两种思路:组合数学,动态规划。
对于这道题若使用动态规划计数,必须将矩阵设入状态,显然不可行,因此考虑组合数学解决问题。
我们先考虑矩阵中不包含障碍点的情况,我们可以得出以下方案数:
将矩阵的值计算出来:
有没有发现,这是一个倒过来的杨辉三角!
因此对于一个$n\times m$的无障碍点矩阵,其方案数为$C_m^n$。
再考虑如何计算有障碍点的方案数,可以采用容斥原理,在这里我们可以使用动态规划来实现。
设$f[i]$为只经过$i$号障碍点的方案数,这样设状态是因为若包含其它障碍点可能会重复计算,非常麻烦。
转移方程的意思就是:到达$i$障碍点的所有方案减去所有经过了其左上方所有障碍点然后到达$i$点的方案。
最后答案的计算方法为:
因为可以在最后一行任意位置结束,因此可以在$(n+1,m+1)$添加一个障碍点,最后的方案数就是$f[k+1]$
因为组合数很大,因此需要使用Lucas定理计算。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| #include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; typedef long long LL; inline const LL Get_Int() { LL num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const LL mod=1000003; LL F[mod+2],invF[mod+2]; LL Quick_Pow(LL a,LL b) { LL ans=1; while(b) { if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } LL C(LL n,LL m) { if(m>n)return 0; return F[n]*invF[m]%mod*invF[n-m]%mod; } LL Lucas(LL n,LL m) { if(!m)return 1; return (C(n%mod,m%mod)*Lucas(n/mod,m/mod))%mod; } struct Point { LL x,y; bool operator < (const Point& b) const { return x<b.x||(x==b.x&&y<b.y); } } a[2005]; LL n,m,p,f[2005]; int main() { F[0]=invF[0]=1; for(int i=1; i<=mod; i++) { F[i]=F[i-1]*i%mod; invF[i]=Quick_Pow(F[i],mod-2); } n=Get_Int(); m=Get_Int(); p=Get_Int(); for(int i=1; i<=p; i++) { a[i].x=Get_Int(); a[i].y=Get_Int(); } sort(a+1,a+p+1); a[p+1].x=n+1,a[p+1].y=m+1; for(int i=1; i<=p+1; i++) { f[i]=Lucas(a[i].y-1,a[i].x-1); for(int j=1; j<i; j++) if(a[j].x<a[i].x&&a[j].y<a[i].y)f[i]=((f[i]-f[j]*Lucas(a[i].y-a[j].y-1,a[i].x-a[j].x-1)%mod)%mod+mod)%mod; } printf("%lld\n",f[p+1]); return 0; }
|