题目链接：点击打开链接
题目大意：给出一个类似杨辉三角的菱形，求给定坐标的数值是多少。不难看出，每一个位置的数字就是（左上，右上，正上）这三个数的和。
解题思路：
从（1,1）走到（A,B）一共有多少总方案。
可以左下走（1,0），正下走（2,1），右下走（1,1）。
假设左下走了 x 次，正下走 y 次，右下走 z 次。则得到方程：
（1,1）+ x*（1,0）+ y*（2,1）+ z*（1,1）==（a,b）
求得：
x + 2*y + z == a - 1;
y + z == b - 1;
再得：
x+y=a-b; y+z=b-1; （ y<=min(a-b,b-1) ）枚举y。
那么左下走了 x 次，正下走 y 次，右下走 z 次这样的走法有多少总方案，其实就是一个组合数。
在（x+y+z）中选出 x 次走左下那么就是C（x+y+z,x），在剩下的（y+z）中选出 y 次走正下就是C（y+z，y），最后剩下的就是走 z 次右下C（z,z）==1。
所以方案数就是C（x+y+z,x）* C（y+z,y）==(x+y+z)!/(x!*y!*z!)==(a-y-1)!/((a-b-y)!*y!*(b-y-1)!)。然后枚举 y 全部加起来，结果再乘法逆元下即可。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const ll mod=1000000007; ll arr[100100],qrr[100100]; ll qpow(ll a) { ll b=mod-2,ans=1; a%=mod; while(b) { if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans; } void init() { arr[0]=qrr[0]=1; for(int i=1;i<100100;i++) arr[i]=arr[i-1]*i%mod; for(int i=1;i<100100;i++) qrr[i]=qpow(arr[i]); } int main() { init(); ll a,b; while(~scanf("%lld%lld",&a,&b)) { ll ta=a-b, tb=b-1, minn=min(ta,tb), ans=0; for(ll y=0; y<=minn; y++) ans=(ans+arr[a-y-1]*qrr[y]%mod*qrr[a-b-y]%mod*qrr[b-1-y]%mod)%mod; printf("%lld\n",ans); } return 0; }
