本文共 999 字,大约阅读时间需要 3 分钟。
题意:给你4个点A(0,0),B(p,0),C(m,q),D(m,n)问:A-->D&& B-->C在不相交的情况下有多少种方法
此题在比赛中题目理解错了,英语水平还是太弱,比了几场都没提高,唉
算了还是看题解吧:解决此题就是找出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)
本题还会涉及到(A/B)%C的情况,运用扩展欧几里得求乘法逆元得到结果
由于写过几遍了此公式,不再细讲
代码:
#include#include #include 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(); }}
转载地址:http://tbsgi.baihongyu.com/