1、给出$n,k$，求一个大于等于$n$且最小的数字$m$使得$m$的二进制表示中存在连续$k$个1 。
思路：如果$n$满足，答案就是$n$。否则，依次枚举连续1的位置判断即可。
#include <iostream>
#include <set>
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std; class ConsecutiveOnes
{
public:
long long get(long long n,int k) { const int N=50; int a[N+5];
a[0]=0;
for(int i=1;i<=N;++i)
{
a[i]=(n>>(i-1))&1;
a[i]+=a[i-1];
}
for(int i=k;i<=N;++i) if(a[i]-a[i-k]==k) return n;
long long ans=((n>>k)<<k)|((1ll<<k)-1);
long long tmp=ans;
for(int i=k;i<N;++i)
{
if((tmp>>(i-k))&1) tmp^=1ll<<(i-k);
tmp|=1ll<<i;
if(tmp>=n&&tmp<ans) ans=tmp;
}
return ans;
}
};
2、给出一个整数$X=\prod_{i=0}^{n-1}p_{i}^{a_{i}}$，其中$p_{i}$表示第i个素数，比如$p_{0}=2,p_{1}=3$。问有多少有序数列使得数列中每个数字大于1且所有数字的乘积等于$X$。当$X=6$时有三个，分别是{2,3},{3,2},{6}。其中$1\leq n \leq 50,1\leq a_{i} \leq 50$。
思路：令$f_{i}$表示将$X$表示成$i$个数乘积的方案数。那么$f_{i}=\prod_{k=0}^{n-1}g(a_{k},i)-\sum_{k=1}^{i-1}C_{i}^{k}f_{k}$。其中$g(i,j)$表示将$i$个苹果放在$j$个篮子里的方案数，$C_{i}^{j}$表示组合数。
那么答案$ans=\sum f_{i}$
#include <iostream>
#include <map>
#include <string>
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std; const int N=3005;
const int mod=1000000007; int C[N][N]; int add(int x,int y) {
x+=y;
if(x>=mod) x-=mod;
return x;
} void init()
{
C[0][0]=1;
for(int i=1;i<N;++i) {
C[i][0]=1;
for(int j=1;j<N;++j) {
C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
}
} int calC(int a,int b) {
if(a<b) return 0;
if(b+b>a) b=a-b;
return C[a][b];
} int cal1(int a,int b) {
return calC(a+b-1,b-1);
} int dp[N]; struct OrderedProduct {
int count(vector<int> a)
{
init();
int s=0;
const int n=(int)a.size();
for(int i=0;i<n;++i) s+=a[i];
int ans=0;
for(int i=1;i<=s;++i) {
dp[i]=1;
for(int j=0;j<n;++j) dp[i]=(long long)dp[i]*cal1(a[j],i)%mod;
for(int j=1;j<i;++j) dp[i]=add(dp[i],mod-(long long)calC(i,j)*dp[j]%mod);
ans=add(ans,dp[i]);
}
return ans;
}
};