題目鏈接：點擊查看

題目大意：給出一個 n 和 m ，求滿足條件的數組有多少個

數組包含 n 個元素

每個元素的取值為 1 ~ m

包含且僅包含一對相同的元素

存在一個位置 pos ，使得 [ 1 , pos ] 內嚴格遞增，[ pos , n ] 內嚴格遞減

題目分析：讀完題后不難看出是一道排列組合的題目，本著先選數，再排序的原則，我們一步步分析

首先我們需要選出 n 個元素才能構成一個數組，因為需要有一對相同的元素，因此這里我們暫時只需要選出 n - 1 個元素就足夠了，共 C( m , n - 1 ) 種情況，因為題目中需要保證在 pos 位置的兩側嚴格遞增或遞減，那么說明最大值是唯一的，此時在已經選出的?n - 1 個元素中，減去一個最大值，還剩 n - 2 個元素可以重復一遍，滿足題目中的第三個條件，到這一步為止，我們已經處理完了選數的問題，也就是 C( m , n - 1 ) * ( n -?2 ) 種選取方案

接下來需要分析順序問題，相對于選數問題來說，順序可能稍微有一丟丟難度，不過一步一步來還是問題不大的，首先我們現在已經選出了?n 個滿足前三個條件的元素了，因為滿足嚴格遞增和嚴格遞減的限制，所以重復的那個數，以及最大值，這三個數的相對位置都是固定不變的，一定滿足最大值位于最中間，而重復的兩個值分別位于兩側，其他的 n - 3 個數可能會如何分布呢，無非是在最大值的左側或右側兩種情況，我們可以發現，如果這 n - 3 個數在左側或右側的情況固定下來之后，因為題目中第四個條件的限制，數組的順序也隨之固定下來了，且是唯一的，這樣關于順序的方案數也就呼之欲出了：pow( 2 , n - 3 )

其實看題解的話這個題目的難度并不是很大，我感覺難就難在，考慮順序的時候，可能會陷入如何分配最大值的位置的陷阱中去，也就是從絕對位置的方向出發，從而越走越偏，其實不然，因為如果考慮絕對位置的話會使題目復雜化，所以我們不妨從相對位置下手，會起到事半功倍的效果

實現代碼的話也沒什么難度，需要用到的數論知識就是關于逆元的求法了，因為組合數涉及到了取模以及除法，而給出的模數是一個質數，所以直接費馬小定理求逆元然后亂搞就好了

代碼：

#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<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=110;const int mod=998244353;LL q_pow(LL a,LL b) {if(b<0)return 0;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) {LL ans1=1;//分子 LL ans2=1;//分母 for(int i=0;i<m;i++){ans1=ans1*(n-i)%mod;ans2=ans2*(i+1)%mod;}ans2=q_pow(ans2,mod-2);return ans1*ans2%mod; } //C(m,n-1)*(n-2)*pow(2,n-3); int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);printf("%lld\n",C(m,n-1)*(n-2)%mod*q_pow(2,n-3)%mod);return 0; }

?

總結

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

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