首页 > 其他分享 >计算系数

计算系数

时间:2022-10-06 11:23:30浏览次数:53  
标签:系数 int d% long 10007 计算 ksm include

1:使用杨辉三角

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=10007;
int a,b,k,n,m;
int c[1011][1011];
void dt(int x)
{
	c[0][0]=1;
	for(int j=1;j<=x;j++)
	//J为行 
	for(int i=0;i<=j;i++)
	//i为列 
	{
		
			if(i==0) 
			   c[i][j]=1;
			else
		     	c[i][j]=(c[i][j-1]+c[i-1][j-1])%mod;
	}
}
int dd(int x,int p)
{
	int ans=1;
	while(p)
	{
		if(p%2==1) ans=ans*x%mod;
		p/=2;
		x=x*x%mod;
	}
	return ans%mod;
}
main(){
	cin>>a>>b>>k>>n>>m;
	dt(k);
	cout<<(dd(a,n)%mod*dd(b,m)%mod*c[n][k])%mod;
	return 0;
}

  2:使用费马小定理找逆元

#include<iostream>
#include<cstdio>
using namespace std;
long long ksm(long long a,long long b)
{
    if(b==0) return 1;
    if(b%2==0) return ksm(a,b>>1)*ksm(a,b>>1)%10007;
    else return a*ksm(a,b>>1)*ksm(a,b>>1)%10007;
}

int main()
{
    int a,b,k,n,m;
    scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
    int x=1,y=1;
    for(int i=1;i<=n;i++)  //算出分母的值
        x=x*i%10007;
    for(int i=k-n+1;i<=k;i++) //算出分子的值
        y=y*i%10007;
   //因为x^10006 mod 10007=1,于是给分子、分母分别乘上x^10005即可消去分母
    y=y*ksm(x,10005)%10007;
    y=y*ksm(a,n)*ksm(b,m)%10007;
    printf("%d",y);
    return 0;
}

  3:预处理出1到N的逆元

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
long long ni[100100];
void prepare(int x)
{
    ni[1]=1;
    for (int i=2;i<=x;i++)
        ni[i]=(mod-mod/i)*ni[mod%i]%mod;
    return;
}

long long ksm(long long a,long long b)
{
    if(b==0)return 1;
    if(b%2==0)return ksm(a,b>>1)*ksm(a,b>>1)%mod;
    else return a*ksm(a,b>>1)*ksm(a,b>>1)%mod;
}
int main()
{
    int a,b,k,m,n;
    cin>>a>>b>>k>>n>>m;
    prepare(n); 
    int d=1;
	for (int i=1;i<=n;i++)
		d=d*(k-i+1)%mod*ni[i]%mod;
	d=d*ksm(a,n)*ksm(b,m)%mod;
    cout<<d;
}

  

标签:系数,int,d%,long,10007,计算,ksm,include
From: https://www.cnblogs.com/cutemush/p/16757251.html

相关文章