Description
从(0,0)走到(n,m),没走过一个点(x,y)贡献为C(x,y),求最小贡献和。
Solution
让我们guess一下
走的路线一定是先走长的一边再走短的一边,两条直线
然后就是求组合数了
这个可以递推,除的时候用费马小定理解决
Code
get到了pow更短的写法
一开始m没取模溢出了几发
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<map> 5 #define ll long long 6 using namespace std; 7 const int mod=1e9+7; 8 9 ll pow(ll x,ll k){ 10 ll ret=1; 11 for(int i=k;i;i>>=1,x=x*x%mod) 12 if(i&1) ret=ret*x%mod; 13 return ret; 14 } 15 ll n,m; 16 17 int main(){ 18 scanf("%lld%lld",&n,&m); 19 if(n>m) swap(n,m); 20 m%=mod; 21 ll ans=m+1; 22 23 ll x=1; 24 for(int i=1;i<=n;i++){ 25 x*=(m+i),x%=mod; 26 x*=pow(i,mod-2),x%=mod; 27 ans+=x,ans%=mod; 29 } 30 printf("%lld\n",ans); 31 return 0; 32 }