首页 > 代码库 > ARC 058D いろはちゃんとマス目 组合数学
ARC 058D いろはちゃんとマス目 组合数学
题意:n*m矩阵 左下方A*B为禁区,每次可以走下或者左
n,m<=1e5,问从左上到右下不经过禁区时的方案数?
若无禁区,则方案数为C(n+m-2,n-1)
有禁区时 每个合法路径都会到达(n-A,i)i>B 即n-A行的某一列上.
则每个合法路径都可以分成两段,(1,1)->(n-A,i),(n-A,i)->(n,m) (i>B)
注意枚举到(n-A,i)不能向右移动,否则重复枚举.所以路径变为三段.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; const ll mod=1e9+7; ll f[N],n,m,A,B; ll powmod(ll x,ll n) { ll s=1; while(n) { if(n&1) s=(s*x)%mod; x=(x*x)%mod; n>>=1; } return s; } ll C(ll n,ll m) { ll a=f[n],b=(f[m]*f[n-m])%mod; return (a*powmod(b,mod-2))%mod; } int main() { f[0]=1; for(ll i=1;i<N;i++) f[i]=(f[i-1]*i)%mod; while(cin>>n>>m>>A>>B) { ll res=0; for(ll i=B+1;i<=m;i++) { ll tmp=(C(i-1+n-A-1,n-A-1)*C(m-i+A-1,m-i))%mod; res=(res+tmp)%mod; } cout<<res<<endl; } return 0; }
ARC 058D いろはちゃんとマス目 组合数学
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。