【数论】【组合数】【快速幂】【乘法逆元】洛谷 P2265 路边的水沟

从左上角到右下角，共经过n+m个节点，从其中选择n各节点向右(或者m各节点向下)，所以答案就是C(n+m,n)或者C(n+m,m)，组合数暴力算即可，但是要取模，所以用了乘法逆元。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 typedef long long ll;
 5 #define CONST_MOD 1000000007
 6 ll n,m;
 7 ll pow_mod(ll a,ll p,ll MOD)
 8 {
 9     if(!p) return 1;
10     ll ans=pow_mod(a,p>>1,MOD);
11     ans=ans*ans%MOD;
12     if((p&1)==1) ans=ans*a%MOD;
13     return ans;
14 }
15 ll muls(ll a,ll b)
16 {
17     ll res=1;
18     for(ll i=a;i<=b;i++)
19       res=res*i%CONST_MOD;
20     return res;
21 }
22 ll C(ll a,ll b)
23 {
24     return muls(b+1,a)*pow_mod(muls(1,a-b),CONST_MOD-2,CONST_MOD)%CONST_MOD;
25 }
26 int main()
27 {
28     cin>>n>>m;
29     cout<<C(n+m,n)<<endl;
30     return 0;
31 }