题目链接 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个,所以总方案数就是
得到这个之后,那个式子就可以通过等比数列求和来求了,复杂度O(TKlogn),开ll会炸内存,所以开int
代码实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #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 1l l*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]=(1l l*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]=1l l*(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); } }