3005. 小型组合数

Li Dao

直接用递推式子算

include

using namespace std;
typedef long long LL;
LL C[50][50];
int T;

void solve()
{
LL n,m;
cin>>n>>m;
cout<<C[n][m]<<endl;
return;
}

void init()
{
C[1][0]=1;C[1][1]=1;
for(int i=2;i<=40;i++)
{
C[i][0]=1;
for(int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
}
return;
}
int main()
{
scanf(“%d”,&T);
init();
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

珈乐carol

include

using namespace std;
int main(){
int t;
cin>>t;
long long int sum=0;
int i,j,n,m,k;
for(i=0;i>m>>n;
sum=1;
int a[n];
for(j=0;j<n;j++)a[j]=1;
for(j=0;j<n;j++){
sum*=(m-j);k=0;
while(a[k]==0||(sum%(k+1)!=0)){
k++;
}
if(sum%(k+1)==0){sum/=(k+1);a[k]=0;}}
cout<<”case #”<<i<<”:”<<endl;
cout<<sum<<endl;
}
}

Saitama

杨辉三角

10175101101

用double能过(还是老老实实看大佬怎么写的)

10205101536

include

int nums1[10];
/核心思想:分子全部乘起来太大,那就把分子拆成几个因子(如num1[0]=2122232425,num1[1]=2627282930,以此类推),然后再分别让这几个因子去试除从1到n的数字,能整除就num1[i]/=当前的这个数字,否则就把这个数字保存起来,最后再除(因为可能单独的一个因子除不尽,但是把所有的因子乘起来就可以除的尽这个数字了)/
int main(){
int T;
scanf(“%d”,&T);
for(int i = 0;i<T;i++){
for(int j = 0;j<10;j++){
nums1[j] = 1;//初始化数组
}
int m;
int n;
scanf(“%d %d”,&m,&n);
n = (m-n<n)?m-n:n;
int cnt = 0;
for(int k =m-n+1;k<=m;k++){
if(nums1[cnt]>1000000){
cnt++;//将n-m+1到m的数的乘积拆分为几个因子(每个因子的大小都在1000000左右)
nums1[cnt]=k;
}
else nums1[cnt]
=k;
}
long long div = 1;
int flag = 1;
for(int i =1;i<=n;i++){
flag = 1;
for(int j =0;j<=cnt;j++){//试除,除不尽的就保留(用flag判断这几个因子是否有除的尽的)
if(nums1[j]%i==0){
nums1[j]/=i;
flag = 0;
break;
}
}
if(flag) div=i;
}
long long myReturn = 1;
for(int i =0;i<=cnt;i++){
myReturn
=nums1[i];
}
printf(“case #%d:\n”,i);
printf(“%lld\n”,myReturn/div);
}
}

10205101536

评论区的格式异常的怪,开头核心思想那里并在一坨的数字之间是相乘的关系哈,212223

Li Dao

long long lnt 的出发为什么不能计算?
long long 最大只有10^18-10^19之间(2^63-1)

Li Dao

long long lnt 的出发为什么不能计算?
40!已经是10^47了

cd106224

DP

//dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]
#include <iostream>
#include <string.h>
using namespace  std;
using LL = long long;
LL dp[41][41];
int main() {
    int num;
    cin >> num;
    for (int k = 0; k < num; ++k) {
        int m, n;
        cin >> m >> n;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i <= m; ++i) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
            }
        }
        cout<<"case #"<<k<<":"<<endl;
        cout << dp[m][n] << endl;
    }
    return 0;
}
10195101455

include

int main()
{
int T;
scanf(“%d”, &T);
int t;
for(t = 0; t < T; t++)
{
long long dp[41][41];
dp[0][0] = 0;
int M, N;
scanf(“%d%d”, &M, &N);
int m, n;
for(m = 1; m <= M; m++) dp[m][0] = 1, dp[m][1] = m;
for(m = 1; m <= M; m++) dp[m][m] = 1;
for(m = 2; m <= M; m++)
{
for(n = 1; n < m; n++)
{
dp[m][n] = dp[m-1][n-1]+dp[m-1][n];
}
}
printf(“case #%d:\n%lld\n”, t, dp[M][N]);
}
return 0;
}

初雪樱

include

include

int main()
{
int T;
scanf(“%d”,&T);
for(int i=0;im/2)
n=m-n;
unsigned long long int result=1;
int temp=n;
for(int i=m;i>m-temp;i–)
{
if(i==(n2))
{
result
=2;
n–;
}
else
result*=i;
}
if(n>1)
{
do
{
result/=n;
n–;
}
while(n>1);
}
printf(“case #%d:\n”,i);
printf(“%llu\n”,result);
}

return 0;

}

shwei
#include <iostream>

using namespace std;

const int N = 100;

long long c[N][N];

void init() {
    for (int i = 0; i < N; i ++) {
        for (int j = 0; j <= i; j ++) {
            if (j == 0) c[i][j] = 1;
            else {
                c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
            }
        }
    }
}

int main() {
    int n;
    cin >> n;

    init(); // 预处理

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        cout << "case #" << i << ":" << endl;
        cout << c[a][b] << endl;
    }


    return 0;
}
你当前正在回复 博客/题目
存在问题!