又到了选课的时间了,xhd看着选课表发呆,为了想让下一学期好过点,他想知道学n个学分共有多少组合。c++
时间: 2024-02-19 11:59:10 浏览: 96
(C++)学分查询
可以使用组合数公式求解,假设选k门课,每门课的学分为ci,那么总学分为sum(ci),则学分和为n的方案数为:
C(sum(ci), k)
其中C为组合数,可以通过递推或预处理阶乘的方式求解。具体实现可以参考以下代码:
```c++
#include <iostream>
using namespace std;
const int MAXN = 1005;
const int MOD = 1e9 + 7;
int C[MAXN][MAXN];
void init() {
C[0][0] = 1;
for (int i = 1; i < MAXN; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
}
}
}
int main() {
int n, k;
cin >> n >> k;
int c[k];
int sum = 0;
for (int i = 0; i < k; i++) {
cin >> c[i];
sum += c[i];
}
init();
cout << C[sum][k] << endl;
return 0;
}
```
其中init函数用于预处理组合数,C[i][j]表示从i个元素中选j个的方案数。时间复杂度为O(nk),空间复杂度为O(nk)。
阅读全文