CCPC Changchun 2020 D, Meaningless Sequence题解

听说是签到题。

不难看出设x为i二进制个数下1的个数(还是难的)，则a_i=c^x。那么我们只需要考虑所有0到n的个数。

当n为1111时，可以得到为（1+c）^n次方，那么我们把答案看成两部分一部分是1到111...和1000到n，

那么当si位为1时，可以看成是n去掉前一位后再乘以c，递推得到每一个位置的答案，就是最终的个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4010;
const int mod=1e9+7;
char s[N];
int c;
ll pw[N];
void solve(){
    cin>>s>>c;
    int n=strlen(s);
    pw[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1]*(c+1)%mod;
    }
    ll ans=0,pre=1;
    for(int i=0;i<n;i++){
        if(s[i]=='1'){
            ans=(ans+pre*(pw[n-i-1]))%mod;
            pre=pre*c%mod;
        }
    }
    ans=(ans+pre)%mod;
    cout<<ans<<endl;
}


int main() 
{
    std::ios::sync_with_stdio(false);
    cin.tie(0); 
    cout.tie(0);
    int _=1;
    while(_--){
        solve();
    }
    return 0;
}