[BZOJ4737][lucas]清華集訓2016：組合數問題

BZOJ4737

lucas定理的簡單證明：

C n m % p = C n / p m / p ∗ C n % p m % p % p C_n^m\%p=C_{n/p}^{m/p}*C_{n\%p}^{m\%p}\%p Cnm​%p=Cn/pm/p​∗Cn%pm%p​%p

首先有 ( 1 + x ) p ≡ 1 + x p ( % p ) (1+x)^p \equiv 1+x^p (\%p) (1+x)p≡1+xp(%p)，由費馬小定理易證

又 ( 1 + x ) p ≡ ( 1 + x ) ⌊ n / p ⌋ ∗ p ( 1 + x ) r (1+x)^p\equiv(1+x)^{\lfloor{n/p}\rfloor*p}(1+x)^r (1+x)p≡(1+x)⌊n/p⌋∗p(1+x)r

≡ ( 1 + x p ) ⌊ n / p ⌋ ( 1 + x ) r \equiv (1+x^p)^{\lfloor{n/p}\rfloor}(1+x)^r ≡(1+xp)⌊n/p⌋(1+x)r

二項式定理： ≡ ∑ i = 0 k C ⌊ n p ⌋ i x p i ∑ i = 0 k C r j x j \equiv \sum_{i=0}^k{C_{\lfloor{\frac{n}{p}}\rfloor}^i}x^{pi}\sum_{i=0}^k{C_r^j}x^j ≡∑i=0k​C⌊pn​⌋i​xpi∑i=0k​Crj​xj

左邊第m項系數為 C n m C_n^m Cnm​

右邊第m項系數為 C ⌊ n p ⌋ i C r j ( p i + j = m , j < p ) C_{\lfloor{\frac{n}{p}}\rfloor}^i C_r^j(pi+j=m,j<p) C⌊pn​⌋i​Crj​(pi+j=m,j<p)

p i + j = m pi+j=m pi+j=m看作除法的形式即可得證

對于本題，我們将i,j看作k進制數，則要求i,j的每一位分别構成的組合數之積模k=0

因為是k進制數，且k為質數，是以這樣的組合數不存在k的因子

則必須要求存在某一位，該位上i的數字小于j的數字，這樣這一位的組合數就為0

則數位dp即可

Code：

#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long 
using namespace std;
inline ll read(){
	ll res=0,ff=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') ff=-ff;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*ff; 
}
const int N=1e5+5,inv2=5e8+4;
int t,k;
int l1,l2,lim,p1[N],p2[N],c[205][205],f[N][2][2][2];
ll m,n;
inline void add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
int dfs(int flag,int q,int p,int now){
	if(!now) return flag;
	if(f[now][flag][p][q]!=-1) return f[now][flag][p][q];
	int lim1=(q?(k-1):p1[now]),lim2=(p?(k-1):p2[now]);
	int &tmp=f[now][flag][p][q];
	tmp=0;
	for(int i=0;i<=lim1;i++)
		for(int j=0;j<=lim2;j++)
			add(tmp,dfs(flag|(i<j),q|(i<lim1),p|(j<lim2),now-1));
	return f[now][flag][p][q];
}
int main(){
	t=read();k=read();
	while(t--){
		n=read();m=read();
		l1=l2=0;m=min(n,m);lim=m%mod;
		memset(f,-1,sizeof(f));
		while(n) p1[++l1]=(n%k),n/=k;
		while(m) p2[++l2]=(m%k),m/=k;
		while(l2<=l1) p2[++l2]=0;
		int ans=dfs(0,0,0,l1);
		add(ans,mod-(1ll*(lim+1)*lim%mod*inv2%mod));
		cout<<ans<<"\n";
	}
	return 0;
}