11051:二項係数2

13271 ワード
の意見を打診 せいすう論 注釈 テキストリンク

何の問題ですか。


この係数をアノテーション形式で求める問題.

なくてもあってもいい。


コメント(または星雲)を使用する必要はありません.古典的な解答方法でも完全に解決できます.分子を分母に分ける
#include <stdio.h>
#include <stdlib.h>

unsigned g(unsigned a, unsigned b) {
    if(b==0) return a;
    return g(b, a%b);
}
int main() {
    unsigned N,K,i,j,S=1,t,*k1,*k2;
    scanf("%d %d", &N, &K);
    k1=(unsigned*)calloc(4,N-K);
    k2=(unsigned*)calloc(4,N-K);
    for(i=N;i>K;i--) k1[N-i]=i;
    for(i=N-K;i>0;i--) k2[N-K-i]=i;
    for(i=0;i<N-K;i++) {
        for(j=0;j<N-K;j++) {
            if(k2[i]==1) break;
            t=g(k1[j],k2[i]);
            if(t>1) {
                k1[j]/=t;
                k2[i]/=t;
            }
        }
    }
    for(i=0;i<N-K;i++) S=S*k1[i]%10007;
    printf("%d", S);
}

他人の解答


しかし、きちんと問題を解決するには、メモを書いたほうがいい.
また,パスカルの三角形式でより速く求めることができる.
(nr)=(n−1r−1)+(n−1r)\binom{n}{r} =\binom{n-1}{r-1}+\binom{n-1}{r}(rn​)=(r−1n−1​)+(rn−1​)
#include <stdio.h>
int n,k,c[1001][1001];
int main(){
	scanf("%d %d",&n,&k);
	c[0][0]=1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=k; j++){
			if(j-1<0)
				c[i][j]=c[i-1][j];
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%10007;
		}
	}
	printf("%d",c[n][k]);
}
osori_1010の回答
-> https://www.acmicpc.net/source/21988829

参考文献

  • パスカル三角形の簡単な説明
    -> https://m.blog.naver.com/saomath/221948595533
    • オペレーションアルゴリズム文字列(ラムダ式)
    はんなりPythonの2020年