[noip2011]计算系数+二项式定理证明

大水题，二项式定理即可（忘得差不多了）

对于一个二项式，\((a+b)^n\)的结果为

\(\sum_{k=0}^{k<=n}C_{n}^{k}a^{n-k}b^k\)

证明：

由数学归纳法，当\(n=1\)，左边=\(a+b\),右边=\(C^{0}_{1}a+C_1^1b\)

设\(n=k\)时该式成立，则\(n=k+1\)时，

=\((a+b)^n*(a+b)\)=\(a*\sum_{k=0}^{k<=n}C_{n}^{k}a^{n-k}b^k+b*\sum_{k=0}^{k<=n}C_{n}^{k}a^{n-k}b^k\)

=\(\sum_{k=0}^{k<=n}C_{n}^{k}a^{n-k+1}b^k+\sum_{k=0}^{k<=n}C_{n}^{k}a^{n-k}b^{k+1}\)

=\(\sum_{k=0}^{k<=n+1}C_{n}^{k+1}a^{n-k+1}b^{k+1}\)

markdown真麻烦。。。可能打错一些东西，欢迎拍砖

所以该题代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

#define int long long

using namespace std;

const int mod=10007;

int n,m,k,a,b,inv[mod+10],fac[mod+10];

int ksm(int d,int z) {

	int res=1;

	while(z) {

		if(z&1) res*=d,res%=mod;

		d*=d;d%=mod;

		z>>=1;

	}

	return res;

}

void getinv() {

	for(int i=k-1; i>=1; i--)

		inv[i]=inv[i+1]*(i+1)%mod;

}

int C(int n,int m) {

	return fac[m]*inv[n]%mod*inv[m-n]%mod;

}

signed main() {

	cin>>a>>b>>k>>n>>m;

	inv[0]=1;

	fac[0]=fac[1]=1;

	for(int i=2; i<=mod; i++) fac[i]=fac[i-1]*i%mod;

	inv[k]=ksm(fac[k],mod-2);

	getinv();

	cout<<C(n,k)*ksm(a,n)%mod*ksm(b,m)%mod;

}

巴特西

[noip2011]计算系数+二项式定理证明

最新文章

热门文章