組合數?Cmn?表示的是從?n?個物品中選出?m?個物品的方案數。?
舉個例子，從?(1,?2,?3)?三個物品中選擇兩個物品可以有?(1,?2),?(1,?3),?(2,?3)?這三種選擇方法。?
根據組合數的定義，我們可以給出計算組合數?Cmn?的一般公式：

其中?n!?=?1?×?2?×?·?·?·?×?n?。?
小蔥想知道如果給定?n,?m?和?k?，對于所有的?0?≤?i?≤?n,?0?≤?j?≤?min(i,?m)?有多少對?(i,?j)?滿足?Cji?是?k?的倍數。

輸入格式
第一行有兩個整數?t,?k?，其中?t?代表該測試點總共有多少組測試數據，k?的意義見問題描述。
接下來?t?行每行兩個整數?n,?m?，其中?n,?m?的意義見問題描述。

輸出格式
共 t 行，每行一個整數代表所有的?0?≤?i?≤?n,?0?≤?j?≤?min(i,?m)?有多少對?(i,?j)?滿足?Cji?是?k?的倍數。

數據范圍
n,m≤2000,2≤k≤21,t≤10^4
輸入樣例：
1 2
3 3
輸出樣例：
1

代碼如下：

#include <iostream> using namespace std; const int N = 2010; int c[N][N],s[N][N];int main() {int cnt = 0,k = 0;cin>>cnt>>k;for (int i = 0;i<N;i++)for (int j = 0;j<=i;j++){if (!j) c[i][j] = 1%k;else c[i][j] = (c[i-1][j]+c[i-1][j-1])%k;if (!c[i][j]) s[i][j] = 1;}for (int i = 0;i<N;i++)for (int j = 0;j<N;j++){if(i) s[i][j] +=s[i-1][j];if (j) s[i][j] +=s[i][j-1];if (i&&j) s[i][j] -=s[i-1][j-1];}while(cnt--){int n,m;cin>>n>>m;cout<<s[n][m]<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的AcWing 523. 组合数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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