題目鏈接：點擊查看

題目大意：給出一個n和m，要求我們構造出兩個數組a和b，滿足以下要求：

兩個數組的長度都為m

每個元素的取值都為1~n

對于每一個位置都有a[i]<=b[i]

數組a非降序

數組b非升序

輸出有多少種方案

題目分析：因為涉及到方案數了，所以不是dp就是組合數學，我看大佬們都用dp寫的，奈何我不會dp，就只能用組合數學亂搞了

首先前置知識我們需要知道：

從n個數中任選m個數，這m個數從小到大排列，且可重復選取的方案數為C(n+m-1,m)

證明直接貼圖片吧：

?因為數組a非降序，而數組b非升序，又因為要滿足a[i]<=b[i]，我們可以知道兩個數組之間的約束條件僅僅只由最后一位構成，只需要枚舉最后一位就可以了，枚舉最后一位時統計一下當數組a的最后一位數字為 i 時的答案，此時的答案肯定是利用上述已知公式計算出數組a的方案數乘以數組b的方案數了，記得去重，舉個很簡單的例子，因為1 1 1這個答案在 i 為1時已經計算過了，當 i 為2時，還是會重復計算1 1 1這個排列的，所以我們需要減去前面已經計算過的答案，具體實現看代碼吧，我是先n*n的時間預處理出組合數，然后O(n)時間遞推出答案的

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e3+100;const int mod=1e9+7;LL C[N][N];void init() {for(int i=1;i<N;i++)for(int j=1;j<=i;j++){if(j==1)C[i][j]=i;elseC[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;} }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;init();scanf("%d%d",&n,&m);LL ans=0,pre=0;for(int i=1;i<=n;i++){ans=(ans+(C[i+m-1][m]-pre+mod)%mod*C[m+n-i][m])%mod;pre=C[i+m-1][m];}printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1288C Two Arrays(组合数学)的全部內容，希望文章能夠幫你解決所遇到的問題。

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