比赛回顾 | Setsuna的K数列

没A出来的原因

1.将A集合和K数列区分开思考了,总想着在A集合中插入自由组合的数去形成K数列

(其实当初是总结出了A数列中俩元素之间需要插入2^i-1项,这已经很像二进制数的排列了,但依旧没联想到二进制)

2.不知道n个数中选择任意个数进行自由组合并求和要怎么操作,事实上可以通过二进制来完成。

比如x=10000，x的第i位代表3^i次方，那么10001，10010这样递增下去就能遍历自由组合的所有情况，并让合从小到大排列。

核心思路

观察K数列，寻求n与对应项的关联，不难发现K数列的本质就是K进制每个进制位取1或取0，n的二进制表示即为K进制中对应位的进制位。

代码块

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll myPow(ll a,ll b,ll mod){//3^1010
    ll sum=1,t=a;
    while(b){
        if(b&1)    sum=(sum*t)%mod;
        t=(t*t)%mod;
        b>>=1;
    }
    return sum;
}
int main(){
    ll n,k;cin>>n>>k;
    const ll mod = 1e9+7;
    ll ans=0;
    for(int i=0;i<40;i++){//1e9差不多2^32次方,40次应该可以
        if(n & (1ll<<i)){//这里的1也要是ll的1,因为运算结果会超过int
            ans=(ans+myPow(k,i,mod))%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}