UOJ 275. 【清华集训2016】组合数问题

组合数 $C_n^m $表示的是从 \(n\) 个物品中选出 \(m\) 个物品的方案数。举个例子，从$ (1,2,3)(1,2,3)$ 三个物品中选择两个物品可以有 \((1,2),(1,3),(2,3)\) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数$ C_m^n$的一般公式：

其中 \(n!=1×2×⋯×n\)。（额外的，当 n=0n=0 时， n!=1n!=1）

小葱想知道如果给定$ n,m$ 和 \(k\)，对于所有的 \(0≤i≤n,0≤j≤\min\{i,m\}\)有多少对 \((i,j)\) 满足 \(C_i^j\)是 \(k\) 的倍数。

答案对 \(10^9+7\) 取模。

输入格式

第一行有两个整数 \(t,k\)其中 \(t\) 代表该测试点总共有多少组测试数据。

接下来 \(t\) 行每行两个整数 \(n,m\)。

输出格式

\(t\) 行，每行一个整数代表所有的 \(0\leq i\leq n,0\leq j\leq \min \left \{ i, m \right \}\) 中有多少对$ (i,j)\(满足\)C_i^j$是 \(k\) 的倍数。

限制与约定

对于\(100\%\) 的测试点， \(1\leq n,m\leq 10^{18},1 \leq t,k\leq 100\)，且 \(k\) 是一个质数。

\(\\\)

首先考虑使用卢卡斯定理：

迭代过程中只要有一位上的\(\binom{n\%k}{m\%k}=0\)那么最后的组合数就是\(k\)的倍数。当\(n<k,m<k\)时，只有\(n<m\)的情况下：\(\binom{n}{m}=0\)。

我们将\(n,m\)写成\(k\)进制的数，然后做数位\(DP\)。先不考虑\(j\leq i\)的限制的话要好做一些，然后在减掉\(j>i\)的情况（这部分显然为0）就好了。

代码（小心爆\(long\ long\)）：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

inline ll Get() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

const ll mod=1e9+7;

ll n,m,k;

ll A[100],B[100];

int d;

#define pr pair<ll,ll>

#define mp(a,b) make_pair(a,b)

pr f[100][2][2];

pr dfs(int v,int flag1,int flag2) {

	if(v<0) return mp(0,1);

	if(f[v][flag1][flag2].first!=-1) return f[v][flag1][flag2];

	int u1=(!flag1)?k-1:A[v],u2=(!flag2)?k-1:B[v];

	ll ans0=0,ans1=0;

	pr now;

	for(int i=0;i<=u1;i++) {

		for(int j=0;j<=u2;j++) {

			now=dfs(v-1,flag1&&i==u1,flag2&&j==u2);

			if(i<j) {

				(ans0+=1ll*now.first+now.second)%=mod;

			} else {

				(ans0+=now.first)%=mod;

				(ans1+=now.second)%=mod;

			}

		}

	}

	f[v][flag1][flag2]=mp(ans0,ans1);

	return mp(ans0,ans1);

}

ll cal(ll l,ll r) {return 1ll*(l+r)*(r-l+1)/2%mod;}

int main() {

	int T=Get();

	k=Get();

	while(T--) {

		n=Get(),m=Get();

		d=0;

		ll mx=max(n,m);

		while(mx) {

			d++;

			mx/=k;

		}

		d--;

		ll x=n;

		for(int i=0;i<=d;i++) {

			A[i]=x%k;

			x/=k;

		}

		x=m;

		for(int i=0;i<=d;i++) {

			B[i]=x%k;

			x/=k;

		}

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

			for(int a=0;a<=1;a++)

				for(int b=0;b<=1;b++) f[i][a][b]=mp(-1,-1);

		pr ans=dfs(d,1,1);

		ans.first=(ans.first-cal(max(1ll,m-n)%mod,m%mod)+mod)%mod;

		cout<<ans.first<<"\n";

	}

	return 0;

}