二进制问题--数位dp/组合数

P8764 [蓝桥杯 2021 国 BC] 二进制问题 - 洛谷

1.组合数算法

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
ll n,k;
ll f[64][64];
vector<int> a;
void init()///求组合数数组 
{for(int i=0;i<=n+1;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];}}
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>k;while(n)///将n转成2进制形式，同时得到n的数位 {a.push_back(n%2);n/=2;}n=a.size();init();///组合数 int last=0;///last表已经过去/固定的1，正在遍历的不算 ll res=0;for(int i=n-1;i>=0;i--)///遍历n，从左到右 {if(a[i])///如果这位是1，那么我假设他为0，后面就得取k-last个1 ///1.是不是小于n 2.是不是全部情况  3.是不是不会重复///cab   a为取1的个数，b为总位数（遍历到i，那么i后面有i位，因为从0开始数的///不会重复，因为last会变///一直遍历0不就不变了？一直遍历0你res答案也没变啊 {res+=f[i][k-last];last++;if(last==k) ///last=k，那么就只有一种情况了，直接加上break'结束 {res++;break;	}}}cout<<res;return 0;
}

2.数位dp写法：

参考洛谷最后一篇题解

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
ll n,k;
ll b;///表示进制
vector<int> a; 
ll dp[64][64];
ll dfs(ll pos,ll tot,bool ismax)
{if(pos==-1)///pos从n-1到0，pos==-1代表已经全部遍历///这时候如果tot==k说明这是一种情况，+1///反之，不是，+0 {if(tot==k) return 1;return 0;}	ll maxn;if(ismax) maxn=a[pos];else maxn=b-1;///判断当前最大是///如果上一位是最大，那么他只能是n的对应值？！？！ if(!ismax&&dp[pos][tot]!=-1) return dp[pos][tot];///不是最大值才具有普遍性ll res=0;for(int i=0;i<=maxn;i++){if(tot==k){res++;break;}else{if(i) res+=dfs(pos-1,tot+1,ismax&&i==maxn);///重点在ismax这里刚开始我是认为i==maxn就可以，发现这样会少很多情况///即当上一位是ismax且这位也是ismax才能代表当前的全部情况else res+=dfs(pos-1,tot,ismax&&i==maxn);}} if(!ismax) return dp[pos][tot]=res;///不是ismax就代表了0000-xxxx的全部情况 return res;
} 
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);b=2;cin>>n>>k;memset(dp,-1,sizeof(dp));while(n){a.push_back(n%2);n/=2;}cout<<dfs(a.size()-1,0,true);return 0;
}