【UOJ#275】组合数问题（卢卡斯定理，动态规划）

题面

UOJ

题解

数据范围很大，并且涉及的是求值，没法用矩阵乘法考虑。

发现\(k\)的限制是，\(k\)是一个质数，那么在大组合数模小质数的情况下可以考虑使用卢卡斯定理。

卢卡斯定理写出来是\(Lucas(n,m)=Lucas(n/K,m/K)*Lucas(n\%K,m\%K)\)

显然只要有任何一个\(Lucas(n\%K,m\%K)=C_{n\%K}^{m\%K}\)是\(K\)的倍数那么当前数就会是\(K\)的倍数。因为\(K\)是质数，并且组合数的上下都小于\(K\)，因此这个值是\(K\)的倍数的时候，当且仅当\(m\%K>n\%K\)。那么整个式子我们理解为，把\(n,m\)按照\(K\)进制分解，当且仅当存在至少一位上有\(m\)的这一位大于\(n\)的这一位成立。分解为\(K\)进制之后最多\(logn\)大概是\(60\)位，可以大力考虑\(dp\)。

设\(f[i][0/1][0/1][0/1][0/1]\)表示当且考虑到了第\(i\)位，第一个数是否卡在上界\(n\)，第二个数是否卡在上界\(m\)，第二个数是否卡在上界第一个数，前面是否至少已经存在一位满足第二个数大于第一个数了。这样子\(dp\)好复杂，我们用总方案减去不合法的，设\(f[i][0/1][0/1]\)表示当且是否卡在边界上，强制没有任何一位满足第二个数大于第一个数。总数很好算，减一下就好了。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MOD 1000000007

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

long long n,m;int T,K,f[65][2][2],sn[65],tn,sm[65],tm,ans;

int main()

{

	cin>>T>>K;

	while(T--)

	{

		cin>>n>>m;m=min(n,m);tn=tm=0;

		ans=(((1+m)%MOD)*(m%MOD)%MOD*500000004%MOD+((n-m+1)%MOD)*((m+1)%MOD)%MOD)%MOD;

		for(;n;n/=K,m/=K)sn[++tn]=n%K,sm[++tm]=m%K;

		memset(f,0,sizeof(f));f[tn+1][1][1]=1;

		for(int i=tn;i;--i)

			for(int j=0;j<2;++j)

				for(int k=0;k<2;++k)

					if(f[i+1][j][k])

						for(int x=0;x<=(j?sn[i]:K-1);++x)

							for(int y=0;y<=(k?sm[i]:K-1)&&y<=x;++y)

								add(f[i][j&(x==sn[i])][k&(y==sm[i])],f[i+1][j][k]);

		for(int i=0;i<2;++i)

			for(int j=0;j<2;++j)

				add(ans,MOD-f[1][i][j]);

		printf("%d\n",ans);

	}

	return 0;

}