CodeForces - 914C(組合數學+dp)

Travelling Salesman and Special Numbers

題目傳送門

題意:給一個數n(二進制表示)和k，要求你在[1,n]中找到特殊數字個數，特殊數字能經曆k次operations轉化得到1。One opertion:該數(二進制)中有X個1則轉化為X(十進制)。

思路:n的範圍超級大，但經過一次operation後縮小到[1,1000]以内，并且對于這個範圍，我們可以直接暴力得出[1,n]轉化為1所需的次數book[1,1000]。因為縮減範圍，是以我們要在book[1,1000]找到符合k-1的下标i，然後考慮i個1形成的二進制數的情況以及大小。不考慮形成的數的大小，我們可以預處理對于每一位有放1或者不放的情況數量，則有dp[i]{j}=dp[i-1]{j}+dp[i-1]{j-1}。要使得到的數小于n，我們則隻需考慮n中二進制位為1的位置取還是不取即可。注意要特判。

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <functional>
#define inf 10000000
using namespace std;
typedef long long ll;
const int MAXN=+;
const int MAX=+;
const double eps=;
const int MOD=+;

string s;
ll k;
ll book[MAX],dp[MAX][MAX];
ll ans;

void init(){
    for(int i=;i<=;i++){
        ll temp=i;
        ll t,countt=;
        while(temp>){
            ll cnt=;
            t=temp;
            while(t){
                if(t%==)  cnt++;
                t=t/;
            }
            temp=cnt;
            countt++;
        }
        book[i]=countt;
    }
    for(int i=;i<=;i++)
        dp[i][]=;
    for(int i=;i<=;i++){
        for(int j=;j<=i;j++){
            dp[i][j]=(dp[i-][j]+dp[i-][j-])%MOD;
        }
    }
}

ll Dp(ll pos,ll num){
    if(pos>=s.size())
        return ;
    ll cnt=;
    if(s[pos]=='1'){
        cnt=dp[s.size()-pos-][num];
        if(num==){
            return (cnt+)%MOD;
        }
        else
            return (cnt+Dp(pos+,num-))%MOD;
    }
    else
        return (cnt+Dp(pos+,num))%MOD;
}

int main(){
    #ifdef ONLINE_JUDGE
    #else
    freopen("in.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    #endif

    init();
    cin>>s>>k;
    if(k==){
        cout<<<<endl;
        return ;
    }
    if(k==){
        cout<<s.size()-<<endl;
        return ;
    }
    if(s=="1"){
        cout<<<<endl;
        return ;
    }
    ll ans=;
    for(int i=;i<=s.size();i++){
        if(book[i]==k-){
            ans+=Dp(,(ll)i)%MOD;
            ans=ans%MOD;
        }
    }
    cout<<ans<<endl;

    return ;
}