题目分析

首先我们打出一张地图： 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70 别告诉我你对这张图没有任何想法，如果你确实没有想法，说明你与组合数还不够亲近。。。事实上，把图旋转45度后可以得到一个杨辉三角（意会可证），因此我们发现第x行y列的数就是 Cxx+y 。 然后我们脑补可知，假如m>n，我们就先沿着长边走m步，然后再沿着短边走。 所以得到答案就是 m+Cnm+n+1 （ Cm+1m+n+1=∑ni=0Cmm+i=Cnm+n+1 ，欲知如何证明，请看我曾经一篇总结组合数性质的博客:走你╭(′▽`)╯。) 好，然后你会发现这题其实可以直接上公式求的。。。然而。。。你就WA了4个点。。。 你会迷茫。。。会怀疑人生，怀疑鲁迅，怀疑枣树。。。 于是，你轻轻地将long long改成了unsigned long long，然后，你得到了这个点的正确结果。。。 你会提交，会发现，WA的点更多了。。。 你会怀疑出题人，怀疑世界，怀疑鲁迅，怀疑枣树。。。 于是你会去搜题解，你发现别人都是用的Lucas，并且没有开unsigned long long。 这时候，你会写Lucas，并A掉这题。 （boshi体结束） 天哪这题数据炸了long long！！！因为Lucas的蜜汁原因会有4个点不会炸！！！什么鬼标程。

代码

#include<iostream> #include<cstdio> #include<climits> #include<cstring> #include<algorithm> using namespace std; #define LL long long LL mod=1000000007; LL ksm(LL x,LL y){ LL re=1; while(y){ if(y&1)re=re*x%mod; x=x*x%mod,y>>=1; } return re; } LL C(LL m,LL n){ LL s1=1,s2=1; for(LL i=m-n+1;i<=m;i++)s1=s1*i%mod; for(LL i=1;i<=n;i++)s2=s2*i%mod; return s1*ksm(s2,mod-2)%mod; } LL lucas(LL m,LL n){ if(!n)return 1; return lucas(m/mod,n/mod)*C(m%mod,n%mod)%mod; } int main() { LL n,m; scanf("%lld%lld",&n,&m); if(n>m)swap(n,m); printf("%lld",(m+lucas(n+m+1,n))%mod); return 0; }