这是本文档旧的修订版！

牛客练习赛81

比赛链接

C-小Q与构造

题意

求满足如下条件的集合 $S$ 个数：

$x\in S\to 1\le x\le n$
$x\in S,y\in S,x\le y\to y \neq kx,y\neq k^px$

题解

把 $1\sim n$ 拆分成若干条链 $a,ak,ak^2,ak^3\cdots$ 易知每条链之间的选择互不影响，答案即为每条边的答案之积。

对每条链，直接状压 $\text{dp}$，对位置 $i$，如果位置 $i-1,i-p$ 已选则一定不能选，否则任意。

不难发现每条链的答案只有链的长度有关，与首项 $a$ 的具体值无关。另外所有 $k\not\mid i$ 均可以作为链的首项 $a$。

考虑暴力枚举链的长度，显然链的最大长度不超过 $\log_k n$。对每个长度，计算出 $a$ 的上下界然后删去 $k$ 的倍数统计贡献即可。

时间复杂度 $O((2^p+\log n)\log n)$。

查看代码

const int Mod=10086001;
int quick_pow(int a,int k){
	int ans=1;
	while(k){
		if(k&1)ans=1LL*ans*a%Mod;
		a=1LL*a*a%Mod;
		k>>=1;
	}
	return ans;
}
LL my_pow(int a,int k){
	LL ans=1;
	while(k--)ans*=a;
	return ans;
}
const int MAXL=64,MAXP=10;
int dp[MAXL][1<<MAXP],s[MAXL];
int main()
{
	LL n=read_LL();
	int k=read_int(),p=read_int(),S=(1<<p)-1;
	if(k==1){
		enter(1);
		return 0;
	}
	dp[1][0]=dp[1][1]=1;
	s[1]=2;
	_for(i,2,MAXL){
		_for(j,0,1<<p){
			dp[i][(j<<1)&S]=(dp[i][(j<<1)&S]+dp[i-1][j])%Mod;
			if((j&1)==0&&(j&(1<<(p-1)))==0)
			dp[i][(j<<1|1)&S]=(dp[i][(j<<1|1)&S]+dp[i-1][j])%Mod;
		}
		_for(j,0,1<<p)
		s[i]=(s[i]+dp[i][j])%Mod;
	}
	int ans=1;
	for(int i=1;;i++){
		LL lef=n/my_pow(k,i)+1,rig=n/my_pow(k,i-1);
		LL cnt=rig-lef+1-((rig/k)-(lef+k-1)/k+1);
		ans=1LL*ans*quick_pow(s[i],cnt%(Mod-1))%Mod;
		if(lef==1)break;
	}
	enter(ans);
	return 0;
}

CVBB ACM Team

目录

牛客练习赛81

C-小Q与构造

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

牛客练习赛81

C-小Q与构造

题意

题解

页面工具