【DidaOJ】[338]QAQ的问题

问题描述

问题分析

一道排列组合的题目
先从阵地里选出哪几个阵地
然后把士兵让进去允许空
由排列组合的知识得
C(n+m-1,m-1)

需要注意的是%777
所以使用数组
运用 $ CMI[i][j]=CMI[i-1][j-1]+CMI[i-1][j] $
来计算CMI比较好

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h> 
int CMI[101][101]; 
void GetCMI() { 
    for(int i=0; i<=100; i++) 
        CMI[i][0]=1; 
    for(int i=1; i<=100; i++) { 
        for(int j=1; j<=i; j++) { 
            CMI[i][j]=(CMI[i-1][j-1]+CMI[i-1][j])%777; 
        } 
    } 
} 
  
int main() { 
    GetCMI(); 
    int N,M; 
    while(scanf("%d %d",&N,&M)!=EOF) { 
        int sum=0; 
        for(int i=1; i<=M; i++) { 
            sum=(sum+CMI[M][i]*CMI[N+i-1][i-1])%777; 
        } 
        printf("%d\n",sum); 
    } 
    return 0; 
} 

题目地址：【DidaOJ】[338]QAQ的问题)