コンビネーション数の詳細

66102 ワード
数論
概念:組合せ数はC(n,m)で表し,n個の数の中でm個の数を取るスキームを表す.(この概念は主に問題を組合せ数に抽象化するために用いられる).式:組合せ数の式も多くなく、1、C(n,m)=C(n,n-m).2、C(n,m)=C(n-1,m-1)+C(n-1,m).これはとても重要で、これは楊輝三角の繰返し式と同じなので、私たちはよく楊輝三角と組み合わせ数を合わせて見ます.典題3,C(0,n)+C(1,n)+C(2,n)+C(3,n)+...C(n,n)=2^nという式は二次項の定理として用いられ,これもよく用いられる.この上の3つは私たちがよく使うものです(大物を選んで左に曲がります).求法:組合せ数に対する求法が多い:Lucas定理、繰返し、逆元.プッシュ:これは実は楊輝三角をプッシュしています.これは主にnとm<=2000で、多くの場合に使われています.栗を挙げると、このような問題に対して私たちはプッシュに適しています.適用範囲:n<=2000(nは組合せ数の下付きの値、すなわちC(n,m)中のn)である.ボードのサブコード:
#include
#include
using namespace std;
int C[1000][1000],mod=1e9+9;
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<=n;i++)//       
	{
		C[i][1]=i%mod;//  i          i 
		C[i][i]=C[i][0]=1;// i    i         
	}
	for(int i=2;i<=n;i++)//       
		for(int j=2;j<i;j++)//       
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;//       ，            
	printf("%d",C[n][m]);//     
	return 0;
}

タイトルコード:
#include
#include
using namespace std;
long long C[2010][2010],sum[2010][2010],mod;
void pre()
{
	for(int i=0;i<=2000;i++)
	{
		C[i][1]=i%mod;
		C[i][i]=C[i][0]=1;
	}
	for(int i=2;i<=2000;i++)
		for(int j=2;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	for(int i=1;i<=2000;i++)
		for(int j=1;j<=i;j++)//     i   1 j         mod    
			if(C[i][j]==0)//   mod  ，    0  mod    
				sum[i][j]=sum[i][j-1]+1;//      
			else sum[i][j]=sum[i][j-1];//          
	return ;
}
int main()
{
	int n,m,T;
	scanf("%d %d",&T,&mod);//       
	pre();//    2000        
	while(T--)
	{
		long long ans=0;
		scanf("%d %d",&n,&m);
		for(int i=1;i<=n;i++)
			if(i>m)//     ，    i
				ans+=sum[i][m];
			else ans+=sum[i][i];
		printf("%lld
",ans);//     
	}
	return 0;
}

階乗逆元:この方法は組合せ数の定義式に基づいて求め,C(n,m)=n!/(m!*(n-m)!),だから私たちはすべての階乗と逆元を前処理します.まず、逆元の前処理を乗算します.逆元を乗算しない点この適用範囲:nmodの場合、modの倍数で逆元がない場合があります.これは間違っています.
#include
#include
using namespace std;
long long inv[1000100],jc[1000100],mod=1e9+9;
long long pow(long long a,long long b)//    
{
	long long ans=1;
	while(b)
	{
		if(b%2==1)
			ans=(ans*a)%mod;
		a=(a*a)%mod;
		b=b>>1;
	}
	return ans;
}
void pre()
{
	jc[1]=1;//     
	for(int i=2;i<=1000000;i++)
		jc[i]=(jc[i-1]*i)%mod;//    
	inv[1000000]=pow(jc[1000000],mod-2);//        
	for(int i=999999;i>=0;i--)
		inv[i]=(inv[i+1]*(i+1))%mod;//        
	return ;
}
int main()
{
	pre();
	int T;
	scanf("%d",&T);
	while(T--)
	{
		long long n,m;
		scanf("%lld %lld",&n,&m);
		printf("%lld
",(((jc[n]*inv[m])%mod)*inv[n-m])%mod);//   ，  mod，  mod，   mod！ 
	}
}

ボードコード(拡張ユークリッド):
#include
#include
using namespace std;
int mod=1e9+9,inv[1000100],jc[1000100],x,y;
void gcd(int a,int b)//       
{
	if(b==0)
	{
		x=1;
		y=0;
		return ;
	}
	gcd(b,a%b);
	int k=x;
	x=y;
	y=k-a/b*y;
	return ;
}
void pre()
{
	jc[1]=1;
	for(int i=2;i<=1000000;i++)//    
		jc[i]=(jc[i-1]*i)%mod;
	gcd(jc[1000000],mod);//        
	inv[1000000]=(x+mod)%mod;//   
	for(int i=999999;i>=0;i--)//       
		inv[i]=(inv[i+1]*(i+1))%mod;
	return ;
}
int C(int n,int m)
{
	return (((1LL*jc[n]*inv[m])%mod)*inv[n-m])%mod;//    
}
int main()
{
	int T;
	scanf("%d",&T);
	pre();
	while(T--)
	{
		int n,m;
		scanf("%d %d",&n,&m);//   
		printf("%d
",C(n,m));//     
	}
	return 0;
}

Lucas定理:この定理は個人的にはまあまあだと思いますが、主にmodに対しては小さいので、階乗を使うとmodの倍数になる可能性があります.このように逆元で組み合わせ数を求めるとggになります.しかし、プッシュがまた詰まった場合、私たちはこれしか使えません.適用範囲:繰返しと階乗逆元が掛けられている場合、これを使用します.式:Lucas(n,m,mod)(nとmはC(n,m)のうち、modは型取り対象)=C(n%mod,m%mod)*Lucas(n/mod,m/mod,mod).コード:このコードは2種類あります.公式には組み合わせ数がありますが、範囲が下がっただけなので、Lucasの定理で元のカード死の繰返しと階乗の逆元を救い返します.だから私たちは2つのコードを持っています.modが比較的小さい場合,繰返しを用いることができ,modが比較的大きい場合,次乗逆元を用いることができる.プッシュ:
#include
#include
using namespace std;
int C[2010][2010],mod;
void pre()//    
{
	for(int i=1;i<=mod;i++)
	{
		C[i][1]=i%mod;
		C[i][i]=C[i][0]=1;
	}
	for(int i=2;i<=mod;i++)
		for(int j=2;j<i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	return ;
}
int Lucas(int n,int m)
{
	if(m==0)//   
		return 1;
	return (C[n%mod][m%mod]*Lucas(n/mod,m/mod))%mod;//Lucas      
}
int main()
{
	int T;
	scanf("%d %d",&T,&mod);
	pre();
	while(T--)
	{
		int n,m;
		scanf("%d %d",&n,&m);
		printf("%d
",Lucas(n,m));//Lucas   
	}
	return 0;
}

階乗逆元:これには小さな最適化がありますが、modは質量数でなければなりません.そうしないと、mod以内の階乗がmodの倍数ではないことを保証します.フェルマの定理:
#include
#include
using namespace std;
int jc[1000100],inv[1000100],mod;
int pow(long long a,long long b)//    
{
	long long ans=1;
	while(b)
	{
		if(b%2==1)
			ans=(ans*a)%mod;
		a=(a*a)%mod;
		b=b>>1;
	}
	return (int)ans;
}
void pre()//        
{
	jc[1]=1;
	for(int i=2;i<mod;i++)
		jc[i]=(jc[i-1]*i)%mod;
	inv[mod-1]=pow(jc[mod-1],mod-2);//      
	for(int i=mod-2;i>=0;i--)
		inv[i]=(inv[i+1]*(i+1))%mod;
}
int C(int n,int m)//      
{
	return (((jc[n]*inv[m])%mod)*inv[n-m])%mod;
}
int Lucas(int n,int m)
{
	if(m==0)//   
		return 1;
	return (C(n%mod,m%mod)*Lucas(n/mod,m/mod))%mod;//Lucas     
}
int main()
{
	int T;
	scanf("%d %d",&T,&mod);
	pre();
	while(T--)
	{
		int n,m;
		scanf("%d %d",&n,&m);
		printf("%d
",Lucas(n,m));//   
	}
	return 0;
}

ユークリッドを開拓:
#include
#include
using namespace std;
int mod,inv[1000100],jc[1000100],x,y;
void gcd(int a,int b)//       
{
	if(b==0)
	{
		x=1;
		y=0;
		return ;
	}
	gcd(b,a%b);
	int k=x;
	x=y;
	y=k-a/b*y;
	return ;
}
void pre()//    
{
	jc[1]=1;
	for(int i=2;i<mod;i++)
		jc[i]=(jc[i-1]*i)%mod;
	gcd(jc[mod-1],mod);//     
	inv[mod-1]=(x+mod)%mod;//     
	for(int i=mod-2;i>=0;i--)
		inv[i]=(inv[i+1]*(i+1))%mod;
	return ;
}
int C(int n,int m)//      
{
	return (((1LL*jc[n]*inv[m])%mod)*inv[n-m])%mod;
}
int Lucas(int n,int m)
{
	if(m==0)
		return 1;
	return (1LL*C(n%mod,m%mod)*Lucas(n/mod,m/mod))%mod;
}
int main()
{
	int T;
	scanf("%d %d",&T,&mod);//      ，mod   
	pre();
	while(T--)
	{
		int n,m;
		scanf("%d %d",&n,&m);
		printf("%d
",Lucas(n,m));//   
	}
	return 0;
}

补充:この组み合わせ数にはもう一つの超牛折りの原理があります:仕切り板の原理.これは何ですか.実は難しくないです.質問原型:n個の品物をあげます.これらの品物は一毛のように、m-1個の仕切りでmグループに分けます(各グループには品物があります).何種類のプランがありますか.これは組み合わせ数と何の関係がありますか?もちろん関係あります!別の方法で考えてみましょう.このm-1個の仕切り板については、実際にはn-1個の位置を置くことができますが、各方法については1つの案に適切に対応しているので、この問題はm-1個の仕切り板について、n-1個の位置を置くことができます.置く案の数を聞くことができますか.これが組み合わせ数ではないでしょうか.この問題にはもう一つの変形があり、私たちが要求しているのはグループごとに品物があることに気づいたが、もし品物がなければいいのだろうか.実は難しくないです.私たちはこのように考えることができて、すべてのグループのmに対して、私たちはすべて人為的にm個の品物をプラスして、このように上の問題ではありませんか?n+m-1箇所にm-1個の仕切り板を置く.以上がグループ数向上グループのすべての知識であり、皆さんが見て理解してほしい.不明な場合はメッセージでお問い合わせください.
Oracleデータ・ロックのクイック・チェック
EBS開発記録FORM REPORT基本プレイ