文件详细信息

下载本文件

本文件的大小为 2029 字节。

#include<algorithm>
#include<cstdio>
typedef long long ll;
const int P=1000000007;
inline int qmod(const int x){
	return x+((x>>31)&P);
}
inline void add(int&a,const ll b){
	a=(a+b)%P;
}
ll n,m,t;
int k,L,f[51][1600][51],C[51][51],g[51][51][51],lim,tmp;
int main(){
	scanf("%lld%lld%d",&n,&m,&k);//程序中的 $n$、$m$、$k$ 对应者题目中的 $A$、$B$、$n$。
	t=std::max(n,m);
	if(!t){
		puts("1");
		return 0;
	}
	L=63-__builtin_clzll(t);//注意：$t=0$ 时，__builtin_clzll(t) 是未定义行为，小心踩坑！
	f[L+1][n>>L&1][k]=1;
	for(int i=0;i<=k;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++)C[i][j]=qmod(C[i-1][j-1]+C[i-1][j]-P);
	}
	for(int i=0;i<=k;i++)
		for(int j=0;j<=k;j++)
			for(int p=0;p<=j;p++)
				g[i][j][p]=(ll)C[i][p]*C[k-i][j-p]%P;
	lim=(k>>1)*((k+1)>>1)*2;
	//$i$ 为当前考虑的位，要从高到低考虑，因为某一位的异或和加起来之后只会影响更高的位，从高到低枚举就满足了无后效性。
	for(int i=L;i>=0;i--)
		if(m>>i&1)
			for(int j=0;j<=lim;j++)//原本需要 $j$ 个第 $i+1$ 位，更低的位不用管，因为这里管不到。
				for(int p=0;p<=k;p++){//原本有 $p$ 个数顶着上界。
					if(f[i+1][j][p])
						for(int x=0;x<=k;x++)//第 $i$ 位有 $x$ 个 $0$。
							if(j>=x*(k-x)&&(tmp=(j-x*(k-x))<<1|(i?n>>(i-1)&1:0))<=lim)
								//在当前的 $x$ 个顶上界的数中，选 $y$ 个让它的第 $i$ 位变为 $0$，就不再顶上界了。
								for(int y=std::max(x-k+p,0);y<=p&&y<=x;y++)
									//转移的系数为 ${p \choose y} \times {{k-y} \choose {x-y}}$，分别是顶上界和不顶上界的数分别进行选择的方案数。
									add(f[i][tmp][p-y],(ll)g[p][x][y]*f[i+1][j][p]);
				}
		else
			for(int j=0;j<=lim;j++)
				for(int p=0;p<=k;p++)
					if(f[i+1][j][p])
						for(int x=p;x<=k;x++)
							if(j>=x*(k-x)&&(tmp=(j-x*(k-x))<<1|(i?n>>(i-1)&1:0))<=lim)
								add(f[i][tmp][p],(ll)C[k-p][k-x]*f[i+1][j][p]);
	ll ans=0;
	for(int i=0;i<=k;i++)ans+=f[0][0][i];
	printf("%d\n",int(ans%P));
	return 0;
}