小Q与构造

NC219167. 小Q与构造

描述

虽然题目叫做「构造」，但是请相信我，说不定这道题跟构造一点关系都没有呢？

无论是真是假，这叫什么？这还是叫一种生活方式，这是生活所迫，总之都是想象力贫匮的锅。

小 Q 想要为自己出的题在 $\mathrm{lemonQ}$ 评测机上构造数据。

这道题的数据构造方法是这样的：在 $1 \sim n$ 中随便挑选几个数出来成为一个集合。很简单吧。

但是小 Q 出的题有一个非常天才的限制，也就是如果选出的集合是 ${S}$ ，不能存在一个数对 $(x,y)\ \ (其中x\in S, y \in S)$ ，满足 $x=ky$ 或者 $x=k^py$ 。所以说构造一个合情合理的数据是非常难的。

但是小 Q 是一个很有责任心的人，他想要给把自己的题的数据出的更好。于是他将把 $n,k,p$ 给你，想要问，他能构造出多少种符合题目条件的数据？

因为各位都知道这是生活所迫，所以小 Q 好心地，让你求其对 $10086001$ 取模的值。

输入描述

一行三个整数 ，意义如上。

输出描述

一行一个整数，表示能够构造出的数据数对  取模的值。

示例1

输入:

4 2 2

输出:

说明:

一共有 $8$ 种合法的样例，分别是 $\varnothing,\{ 1 \},\{ 2 \},\{ 3 \},\{ 4 \},\{ 1,3 \},\{ 2,3 \},\{ 3,4 \}$ 。

示例2

输入:

1000 5 10

输出:

示例3

输入:

1000000 40 8

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 9ms, 内存消耗: 860K, 提交时间: 2021-04-12 14:25:06

#include <stdio.h>
#include <assert.h>
typedef long long LL;
const LL mod = 10086001;

LL n,k,p;
LL f[64];
LL g[64][1024];

void preprocess(){
	g[0][0] = 1;
	f[0] = 1;
	for(int i=1;i<=60;i++){
		for(int S=0;S<(1<<p);S++){
			if(S&1){
				if(S&2) continue;
				g[i][S] = g[i-1][S>>1];
			}else{
				g[i][S] = (g[i-1][S>>1]+g[i-1][S>>1|(1<<(p-1))])%mod;
			}
			f[i] = (f[i]+g[i][S])%mod;
		}
	}
}

LL qpow(LL bsc,LL y){
	LL ret = 1;
	bsc %= mod;
	while(y){
		if(y&1) ret = ret*bsc%mod;
		bsc = bsc*bsc%mod;
		y >>= 1;
	}
	return ret;
}

LL count(LL l,LL r){
	return (r-l)-r/k+l/k;
}

int main(){
	scanf("%lld%lld%lld",&n,&k,&p);
    if(k==1){
        puts("1");
        return 0;
    }
	preprocess();
	LL ans = 1;
	for(LL x=1,r=n,M=1;r!=0;x++,M*=k){
		LL l=n/(M*k);
		ans = ans*qpow(f[x],count(l,r))%mod;
		r = l;
	}
	printf("%lld\n",ans);
    return 0;
}