题解：P12021 面包题

· · 题解

十分有意思啊。

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

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

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

第一个问题可以简单的 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
*/