C题组合数RE求救

常规
1 
#include<bits/stdc++.h>
using namespace std;

//(n!/m!*(n-m)!)mod q  = (n!mod q)*(1/m!mod q)*(1/(n-m)!mod q)mod q 
int factorial(int x){
	int f=1;
	for(int i=2;i<=x;i++){
		f*=i;
	} 
	return f;
} 
int main(){
	int m,n,q=1e9;
	cin>>n>>m;
	cout<<factorial(n)%q*((1/factorial(m))%q)*((1/factorial(n-m))%q)%q;
	return 0;
}
2 个赞
2

题目是啥

1 个赞
3

C. 组合数

Problem ID: 7851

Contest ID: 5885

必做题

Runtime Error

时间限制：1s 空间限制：256MB

题目描述：

求 Cmn 对 q=109 取模后的值。（注意 n 的范围及其模数）

输入格式：

一行两个整数 n​ 和 m​。(m≤n≤1000​)

输出格式：

一个整数表示答案。

样例输入：

2 1

样例输出：

2

1 个赞
4

q等于109你1e9干嘛

1 个赞
5

复制的原因
image

1 个赞
6

主要代码：

int C(int m, int n){
	if(m>n){
		swap(m,n);
	}
    int cnt = 1;
    for(int i = 0; i < m; i++){
        cnt *= n - i;
        cnt /= i + 1;
    }
    return cnt;
}
1 个赞
7

？

image
image705×144 7.66 KB

1 个赞
10

怎么又来个dfs?

1 个赞
11

不行我那要超时

1 个赞
12

其实本质都在课件上

1 个赞
14

我这样

#include<bits/stdc++.h>
using namespace std;
const int q = 1e9;
long long res[1001][1001] = {0};
long long C(int n,int m){
    if(m == 0 || m == n){
    	return 1;
	}
    if(res[n][m] != 0){
    	return res[n][m];
	}
    return res[n][m] = C(n - 1,m) + C(n - 1,m - 1);
}
int main(){
	int n,m;
	cin >> m >> n;
	cout << C(m,n) % q;
    return 0;
}
1 个赞
16

在等顶针的思路

17

OK

18

@理塘顶针

19

这道题可以用杨辉三角来解决
我使用的是递归
杨辉三角(i,j)位置=(i-1,j)+(i-1,j-1)
于是我们可以得出递推式
还可以使用一个记忆数组，用来提高效率
当j==0或者j==i时，返回1，这样就可以得出递推终止条件
一下是核心部分

long long f(long long n,long long m)
{
	if (m==0 || m==n) 
		return 1;
	if (vis[n][m]) 
		return vis[n][m];
	return vis[n][m]=f(n-1,m)+f(n-1,m-1);
}
1 个赞
20

给个解决方案谢谢:pray:

21

ok

22

我是直接用公式算的

23 
#include<bits/stdc++.h>
using namespace std;
int C(int m, int n){
	if(m>n){
		swap(m,n);
	}
    int cnt = 1;
    for(int i = 0; i < m; i++){
        cnt *= n - i;
        cnt /= i + 1;
    }
    return cnt;
}
int main(){
	int a,b;
	cin >> a >> b;
	cout << C(a,b)%1000000000;
	return 0;
}
1 个赞
24

好像都行