题目

http://172.16.0.132/senior/#contest/show/2068/2

小结

我们发现每个点的点权就是点(0,0)到这个点的方案数。 就是Cn,m。 所以，答案就是

m+1+∑i=1nCi+n,i 但是，我们不能够算这么多次，所以，我们知道一个公式： Cn,m+Cn,m−1=Cn+1,m 所以，我们一开始加上一个C1+n,0， 于是，原数列就变成Cm+n+1,n 然后就用到逆元： ap−1≡1(modp)(费马小定理) ap≡a(modp) ap−2≡1a(modp) bap−2≡ba(modp) 所以，排列组合公式Cn,m= n!m!(n−m)! 于是，这条公式就可以变成 n!m!(n−m)!p−2−1 就好了~

#include<iostream> #include<cstring> using namespace std; long long n,m,ans,a,b,mo; long long ksm(long long a,long long b,long long n) { long long t,y; t=1; y=a; while (b!=0) { if (b&1==1) t=t*y%n; y=y*y%n; b=b>>1; } return t; } int main() { scanf("%lld%lld",&n,&m); if (n>m) { long long t=n; n=m; m=t; } mo=1000000007; ans=(m+1)%mo; long long i; a=1; b=1; for (i=m+n+1;i>=m+2;--i) a=(a*i)%mo; for (i=n;i>=1;--i) b=(b*i)%mo; ans=(ans+(a*(ksm(b,mo-2,mo)%mo))%mo)%mo-1; printf("%lld\n",ans); }