題意：給你4個(gè)點(diǎn)A(0,0),B(p,0),C(m,q),D(m,n)問(wèn)：A-->D&& B-->C在不相交的情況下有多少種方法

此題在比賽中題目理解錯(cuò)了，英語(yǔ)水平還是太弱，比了幾場(chǎng)都沒(méi)提高，唉

算了還是看題解吧：解決此題就是找出A--D&&B-->C的所有情況再減去 ? ?A-->C&&B-->D（即路徑相交的情況）

就是本題要求的答案

公式：C(m+n,n)*C(m-p+q,q) - C(m+q,q)*C(m+n-p,n)?

本題還會(huì)涉及到（A/B）%C的情況，運(yùn)用擴(kuò)展歐幾里得求乘法逆元得到結(jié)果

由于寫(xiě)過(guò)幾遍了此公式，不再細(xì)講

代碼：

#include<stdio.h> #include<math.h> #include<algorithm> using namespace std; typedef long long LL; const LL mod = 100000007; long long a[200005]; LL m,n,p,q,x,y; void init() {a[0] = 1;for(LL i = 1;i <= 200001;i++)a[i] = ( a[i-1] * i )%mod; } void exgcd(LL c,LL b) {if(b == 0){x = 1,y = 0;}else{exgcd(b,c%b);LL tmp = x;x = y;y = tmp - c/b*y;} } void solve() {LL res = (((a[m+n] * a[m-p+q])%mod - (a[m+q]*a[m+n-p])%mod)%mod + mod )%mod;LL ret = ((a[n]*a[m])%mod)*((a[m-p]*a[q])%mod)%mod;exgcd(ret,mod);x = (x+mod)%mod;printf("%lld\n",(x*res%mod)); } int main() {init();while(~scanf("%lld%lld%lld%lld",&m,&n,&p,&q)){solve();}}

總結(jié)

以上是生活随笔為你收集整理的zoj-3624（Count Path Pair）组合数+乘法逆元的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。