档案网站建设书/百度站长快速收录

数位划分做法 

对于 的数，二进制位里恰好有K个1的数的个数为

那么我们将N划分为，对于剩下的，我们可以规定第x位为1，即将转化为,寻找二进制中恰好有K-1个1的数，递减进行即可

#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
const int N=65;
ll f[N][N];
ll n,k;
ll res;
void init(){for(int i=0;i<N;i++)for(int j=0;j<=i;j++){if(!j) f[i][j]=1;else f[i][j]=f[i-1][j-1]+f[i-1][j];}
} 
int main(){cin>>n>>k; init();for(int x=63;x>=0;x--)if(n>>x&1){res+=f[x][k];k--;if(k==0){res++;break;}}cout<<res;
} 

 数位DP做法

                我是标题党，其实我不会hhh，待补

                会了会了

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
ll n;int K;
ll f[75][75];
void init()
{for(int i=0;i<75;i++)for(int j=0;j<i;j++)if(!j) f[i][j]=1;else f[i][j]=f[i-1][j]+f[i-1][j-1];
} 
ll dp(ll n){if(!n) return 0;vector<int> vc;while(n){vc.push_back(n%2);n/=2;}ll res=0;int last=0;for(int i=vc.size()-1;i>=0;i--){int x=vc[i];if(x){res+=f[i+1][K-last];last++;if(last>K) break;}if(!i&&last==K) res++;}return res;
}
int main()
{init();cin>>n>>K;cout<<dp(n);}