Iroha and a Grid

Iroha and a Grid"/>

Iroha and a Grid

题意：开始在(0,0)->(n,m)的只能    右走或下走  且有A×B的禁区不能走。

问你有多少种情况走到右下角。

堕落了，最近都懒得不行，题目英语不想翻译，公式也不想推，以致于做不出来。

这个题目的翻译没做好。以为能    走   上或者左。后来才知道没翻译好，推公式推了很久很久，就是没做出来。

耽误太多时间了，其实可以做一做的。就是不愿意推公式罢了。

以   5行5列，禁区为2行3列为例

1     1     1     1         1
1     2     3     4         5
1     3     6     10     15
0     0     0     10     25

0     0     0     10     35

因为右下角一定是与红色这部分的数字有关。（认真想想即可

但是想要推出答案要更多的数据，这时需要用dp来对拍

9         9        3        3

1    1    1       1    1    1    1    1    1
1    2    3       4    5    6    7    8    9
1    3    6      10    15    21    28    36    45
1    4    10    20    35    56    84    120    165
1    5    15    35    70    126    210    330    495
1    6    21    56    126    252    462    792    1287
0    0    0      56    182    434    896    1688    2975
0    0    0      56    238    672    1568    3256    6231

0    0    0      56    294    966    2534    5790    12021

运用组合数求出红色的数，通过推公式得到    C(n+m-2,m-1);    （n，m是矩阵的行列）

而它的系数推出来是： C(   (a-1)+m-y,  (a-1) );  (a是A禁区的行    ，m是矩阵的列宽，y是当前组合数的列号)

C(7,2)×C(8,3)+C(7,2)×C(9,4)+C(7,2)×C(10,5)+C(7,2)×C(11,6)+C(7,2)×C(12,7)+C(7,2)×C(13,8）

贴上代码自带DP对拍：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 200100;
ll qpow(ll a,ll x){ll ret=1;while (x){if (x&1)ret = ret*a%mod;a=a*a%mod;x>>=1;}return ret;
}
ll fac[maxn],inv[maxn];ll init(){fac[0]=1;for (int i=1;i<maxn;i++)fac[i]=fac[i-1]*i%mod;inv[maxn-1]=qpow(fac[maxn-1],mod-2);for (int i=maxn-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;return 0;
}ll c(ll n,ll m){if (n<m) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{ll n,m,a,b;ll ans=0;init();scanf("%lld%lld%lld%lld",&n,&m,&a,&b);/*int dp[105][105]={0};dp[1][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(i==1&&j==1)continue;if(n-a<i&&i<=n&&1<=j&&j<=b)continue;dp[i][j]=dp[i-1][j]+dp[i][j-1];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%d",dp[i][j]);if(j==m){printf("\n");}else{printf("    ");}}}*/for(ll i=b+1;i<=m;i++){ll x=n-a,y=i;ll p=n-a ,q=m-y+1;ans=(ans+(c(x+y-2,y-1)%mod*c((a-1)+(m-y),a-1))%mod)%mod;}printf("%lld\n",ans);return 0;
}