自动搬运

查看原文

来自洛谷，原作者为

	chenzhaoxu2027 AFOed

搬运于2025-08-24 23:12:11，当前版本为作者最后更新于2025-04-07 17:34:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

十分有意思啊。

我们不妨设一个有 $n$ 个点的无向图，点 $i$ 和点 $j$ 有边（$i<j$）当且仅当 $j = i \times k$。

显然这个图是由很多连通块，每一个连通块都是一根链构成的图。题设中的条件等价于在图中选点使得点不相邻，就是独立集方案数。

每一根链可以分开算，最后再乘法原理乘起来。那么问题就剩两个了：

• 如何求出一个长度为 $n$ 的链的独立集方案数？

• 如何求出有几根长度为 $j$ 的链？

第一个问题可以简单的 DP，设 $f[i]$ 表示长度为 $i$ 的独立集方案数。则要么选第 $i$ 个点，此时有 $f[i-2]$ 种方案；要么不选第 $i$ 个点，此时有 $f[i-1]$ 种方案。多以 $f[i]=f[i-1]+f[i-2]$（就是斐波那契数）。

对于第二个问题，你会发现长度至少为 $i$ 的链上的点的个数就是那些能被 $k^{(i-1)}$ 整除的数。这种数可以 $O(\log_2 n)$ 的计算出来。

紧接着做差分就可以计算出来长度恰好为 $i$ 的链的个数。然后快速幂加乘法原理求解即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 998244353
int n,k;
vector<int> vec;
int dp[100005];
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1){
			res*=a;
			res%=mod;
		}
		a*=a;
		a%=mod;
		b>>=1;
	}
	return res;
}
void slv(){
	cin>>n>>k;
	vec.clear();
	vec.push_back(0);
	int tmp=n;
	while(tmp){
		vec.push_back(tmp-tmp/k);//计算出有几根链长度至少为 i
		tmp/=k;
	}
	for(int i=1;i<vec.size()-1;i++){
		vec[i]-=vec[i+1];
	}
	int ans=1;
	for(int i=1;i<vec.size();i++){
		ans*=qpow(dp[i],vec[i]);
		ans%=mod;
	}
//	cout<<"\n";
	cout<<ans<<"\n";
}
signed main(){
	dp[1]=2;
	dp[0]=1;
	for(int i=2;i<=10005;i++){
		dp[i]=dp[i-1]+dp[i-2];
		dp[i]%=mod;
	}
	int t;
	cin>>t;
	while(t--){
		slv();
	}
	return 0;
}
/*
1 1 2 3 5 8 13 21
*/