題目鏈接：點擊查看

題目大意：給出一個 $n?m$ 的矩陣，其中有 $k$ 個壞點，每次只能向右走或向下走，問從點 $(1,1)$ 到點 $(n,m)$ 共有多少種不同的路線

題目分析：刷知乎看到的一道題，心血來潮就想寫題了

數據范圍 $n,m$ 都是 $1e5$ 級別的，而 $k$ 卻只有 $2000$，所以從壞點入手，考慮 $dp$ 和組合數學

首先對于兩個點 $(x1,y1)$ 和 $(x2,y2)$ 來說，如果沒有壞點的限制，那么這兩個點之間的路線有 $C_{(x2?x1)+(y2?y1)}^{x2?x1}$ 條，下面可以分兩步進行思考，對于每個壞點 $(x,y)$ 來說：

加上點 $(1,1)$ 到點 $(x,y)$ 之間方案數

對于每個滿足 $xx<=x$ 且 $yy<=y$ 的壞點 $(xx,yy)$ 來說，點 $(1,1)$ 經過點 $(xx,yy)$ 然后到達點 $(x,y)$ 的這些路線顯然是不合法的，減去即可

綜上所述，將所有壞點排序之后的轉移方程就是（設 $f_{(x1,y1)}^{(x2,y2)}$ 為壞點 $(x1,y1)$ 到壞點 $(x2,y2)$ 的方案數，$d{p}_i$ 為點 $(1,1)$ 到第 $i$ 個壞點的方案數）：
$$\begin{gathered} d{p}_i=f_{(1,1)}^{(p_i.x,p_i.y)} \\ ?[p_j.x<=p_i.x\&\&p_j.y<=p_i.y]?d{p}_j?f_{(p_i.x,p_i.y)}^{(p_j.x,p_j.y)} \end{gathered}$$
將點 $(n,m)$ 設為第 $k+1$ 個壞點，那么答案自然就是 $d{p}_{k+1}$ 了

代碼：

// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; const int mod=1e9+7; struct Point {int x,y;void input() {read(x),read(y);}bool operator<(const Point& t)const {if(x!=t.x) {return x<t.x;}return y<t.y;} }p[N]; LL dp[N],fac[N],inv[N]; LL q_pow(LL a,LL b) {LL ans=1;while(b) {if(b&1) {ans=ans*a%mod;}a=a*a%mod;b>>=1;}return ans; } LL C(int n,int m) {if(n<m) {return 0;}return fac[n]*inv[m]%mod*inv[n-m]%mod; } void init() {fac[0]=1;for(int i=1;i<N;i++) {fac[i]=fac[i-1]*i%mod;}inv[N-1]=q_pow(fac[N-1],mod-2);for(int i=N-2;i>=0;i--) {inv[i]=inv[i+1]*(i+1)%mod;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int n,m,k;read(n),read(m),read(k);for(int i=1;i<=k;i++) {p[i].input();}p[++k]={n,m};sort(p+1,p+1+k);for(int i=1;i<=k;i++) {dp[i]=C((p[i].x-1)+(p[i].y-1),(p[i].x-1));for(int j=1;j<i;j++) {if(p[i].x>=p[j].x&&p[i].y>=p[j].y) {dp[i]=(dp[i]-dp[j]*C((p[i].x-p[j].x)+(p[i].y-p[j].y),p[i].x-p[j].x)%mod+mod)%mod;}}}write(dp[k]);return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 560E Gerald and Giant Chess(组合数学+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。