文章目錄

• • • 題目解答
    • 題目鏈接

題目解答

來源：acwing

分析：
題目要求：n位數，只能放0，1，2，3；0必須在1前面，2必須在3前面；0不能放在首位。

由于0和1有限制關系，2和3有限制關系，所以把它們分成兩組。總共有n位，用組合數學的角度來考慮。具體思考過程如下圖所示，n位中0和1這一組占多少位，剩下的位數讓2和3來占。

不失一般性，對于A組占k位，B組占n-k位這種情況進行分析：

A組（0和1）占k位，由于0永遠排在1前面，且0不能排在首位，所以A組可取的情況是$C_{n?1}^k$,含義是：在除第一位的情況下，剩下的n-1位中選k位填0或者1，這樣的話，其余的位置就填2或者3.

所以，接著考慮組內問題。對于0和1占k位，假設其中有t個0，則有k-t個1，而且呢，0只能排在1前面，所有組內的情況是和t有關，t至少為1，最大為k-1，所以共有k-1種情況。同理，對于2和3占n-k位，共有n-k-1種情況。

所以，對于對于A組占k位，B組占n-k位這種情況，總共有$C_{n?1}^k\times (k?1)\times (n?k?1)$

則總的情況是${\Sigma }_{k=2}^{n?2}{C}_{n?1}^k\times (k?1)\times (n?k?1)$

如何求組合數呢？參見筆者的另一篇博文：算法刷題-數論-組合數、快速冪、逆元、遞推求組合數、逆元求組合數

ac代碼

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1010; const int mod = 1e9 + 7; int c[N][N];//組合數數組 int n;int main(){cin >> n;//預處理，求組合數 c[i][j]表示i個數中選j個for(int i = 0; i<= n; i++ )for( int j = 0; j<= i; j++)if(!j) c[i][j] =1;else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;LL res = 0;for(int k = 2; k <= n-2; k++)res = (res + (LL)c[n-1][k] * (k-1) * (n-k-1) % mod) % mod;cout << res <<endl; }

題目鏈接

https://www.acwing.com/problem/content/3198/

總結

以上是生活随笔為你收集整理的CSP认证201312-4有趣的数[C++题解]：组合数、数学的全部內容，希望文章能夠幫你解決所遇到的問題。

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