題目
傳送門 to HDU
思路
《嘗試集》
顯然是要減去所有相交的路徑，
考慮列舉最后一個相交的點，那么其前面可以亂走，后面必須不相交，
用 表示，從 走到 和 的不相交——除了在起點 上相交——的路線數量，則
這個式子的意義是列舉最后一個相交的點，把 換成 ，把 換成 ，把 換成 ，把 換成 ，把 換成 ，我們有
那么這道題中，我們需要計算
兩個式子的形式挺相近的，但是我化簡不動了，不過講道理肯定是正確的式子，
《飛鳥集》
考慮兩條相交的路徑，如果不考慮對應關系，它更像一個亂糟糟的毛線團——前面有兩個端頭，后面也有兩個端頭，中間攪在一塊，
當然，我們可以先把毛線團的結構確定，然后再把顏色染上去，所以我們可以 交換對應關系，不難發現相交的路徑數量就是 ，
代碼
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
typedef long long int_;
inline int readint(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
inline void writeint(int x){
if(x > 9) writeint(x/10);
putchar((x%10)^48);
}
inline int qkpow(int_ b,int q,int m){
int ans = 1;
for(; q; q>>=1,b=b*b%m)
if(q&1) ans = ans*b%m;
return ans;
}
const int MaxN = 200005;
const int Mod = 1e9+7;
int jc[MaxN], inv[MaxN];
void prepare(){
jc[1] = inv[1] = 1;
for(int i=2; i<MaxN; ++i){
jc[i] = 1ll*jc[i-1]*i%Mod;
inv[i] = (0ll+Mod-Mod/i)*inv[Mod%i]%Mod;
}
for(int i=2; i<MaxN; ++i)
inv[i] = 1ll*inv[i]*inv[i-1]%Mod;
jc[0] = inv[0] = 1;
}
int_ C(int n,int m){
if(n < m) return 0; // 拿不出來
return 1ll*jc[n]*inv[m]%Mod*inv[n-m]%Mod;
}
int main(){
prepare();
for(int T=readint(); T; --T){
int x1 = readint(), x2 = readint();
int y1 = readint(), y2 = readint();
int_ all = C(x1+y1,y1)*C(x2+y2,y2)%Mod;
int_ bad = C(x1+y2,y2)*C(x2+y1,y1)%Mod;
all = (all+Mod-bad)%Mod;
printf("%lld\n",all);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/1485.html
標籤：區塊鏈
下一篇：棋盤問題（dfs，遞回）