HDU6732

题目链接

HDU6732

思路

这道题首先要会卢卡斯定理和一定的离散知识，根据卢卡斯定理，组合数$C(n,m) mod p$相当于n,m转换为p进制之后每一位的组合数再相乘起来。
然后不等于0的情况就是n转换为p进制后大于m转换为p进制后每一位上的数字都比m的大。然后HMBB[i][j]矩阵相当于若有上述情况，则存在一条路径从i->j,K次方的话，就是i->j经过k条路的方案数目。相当于对n，m的每一位来说存在这样一个序列$t_0->t_1->\dots->t_k$,并且这个序列是单挑不递减的，这个序列存在的方案数就是这个矩阵的和，这个序列可以用组合数学。相当于p个箱子，k+1个球，箱子可以为空的方案数，然后转换成p个箱子，k+p+1个球，箱子不为空的情况。接下来把球拍成一行，然后想象一下在球与球之间使用隔板，就可以把它分成p个部分，一共为k+p+1个隔板，选p-1个，所以总方案数就是

$$F[i][j]=(C_{j+p}^{p-1})^i$$

得到这个之后，那个式子就可以通过等比数列求和来求了，复杂度O(TKlogn),开ll会炸内存，所以开int

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define eps 1e-12
#define gcd(a,b) __gcd(a,b)
const int N = 1e5+10;
bool vis[N*30];
int prime[N*30],cnt; 
int fac[N*20];
int inv[N*20];
void init(){
	for(int i=2;i<N*30;i++){
		if(!vis[i])prime[cnt++]=i;
		for(int j=0;j<cnt&&i*prime[j]<N*30;j++){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0)break;
		}
	}
}
ll quick_pow(ll x,ll k)
{	ll res=1;	
	while(k)
	{
	if(k&1)res=res*x%mod;
    x=x*x%mod;
    k>>=1;
	}
	return res;
}
ll C(int n,int m){
	return 1ll*fac[n]*inv[n-m]%mod*inv[m]%mod;
}
int main(){
	init();
   int t;
   scanf("%d",&t);
   fac[0]=1;
   for(int i=1;i<N*20;i++)fac[i]=(1ll*fac[i-1]*i)%mod;
   inv[N*20-1]=quick_pow(fac[N*20-1],mod-2);
   for(int i=N*20-2;i>=0;i--)inv[i]=1ll*(i+1)*inv[i+1]%mod;
   while(t--){
   	int c,n,k;
   	scanf("%d %d %d",&c,&n,&k);
   	ll ans = 0;
   	ll p = prime[c-1];
   	for(int i=1;i<=k;i++)
	{
   	ll q = C(i+p,p-1);
   	if(q==1)ans=(ans+n)%mod;
   	else{
   	ll fz = q*(1-quick_pow(q,n))%mod;
   	fz=(fz+mod)%mod;
   	ans=(ans+fz*quick_pow(1-q,mod-2)%mod)%mod;
    }
	}
	printf("%lld\n",(ans+mod)%mod);
   }	
}