构造一个长度为N的只有‘0’和‘1’的串s，满足K个限制（s[A,B]中含有C个1），且这个串在所有满足限制的合法串当中为字典序第P大.
状压dp,f[i][j]：假设前i个字符已固定，且这前i个中最后16个字符为j时的合法方案数（注意j前面的到底是什么我们不用管，反正看作前缀是固定的，而这个结果统计的是前缀之后的部分可以有多少种变化）。我们从后往前转移，最终得到每个位置的情况。如何转移看代码就很清楚了，再次感到熟练位操作对做状压方面的题目很重要。
官方题解开头就讲到固定前缀的合法方案数与字典序第p大的关系，一开始没理解...就是如果串是i开头的话（我们以字典序的顺序来尝试i），f[1][i]>=p,那么第p大就一定是在这f[1][i]方案中了，否则从P中减掉f[1][i]（f[1][i]的方案里都是些比P小的啊，减掉f[1][i]之后的P（用P'表示吧）就是开头字典序比i大时的方案里第p'大的，也是原来那个第P大的）,i再转向下一个字典序更大的选择。然后可以一个一个位置构造出这个串。
#include<bits/stdc++.h>
using namespace std;
long long f[105][1<<16];
vector <pair<int,int> > limits[105];
int cnt[1<<16];
int shl[1<<16];
bool check(int i,int last){
for(int j=0;j<limits[i].size();++j){
if(cnt[((1<<limits[i][j].first)-1)&last]!=limits[i][j].second){
return false;
}
}
return true;
}
int main(){
int T,kase=0;
scanf("%d",&T);
for(int i=1;i<(1<<16);++i){
cnt[i]=cnt[i>>1]+(i&1);
shl[i]=(i<<1)&((1<<16)-1);
}
while(T--){
int n,k;
long long p;
scanf("%d%d%lld",&n,&k,&p);
for(int i=1;i<=n;++i) limits[i].clear();
for(int i=1;i<=k;++i){
int A,B,C;
scanf("%d%d%d",&A,&B,&C);
limits[B].push_back(make_pair(B-A+1,C));
}
for(int i=0;i<(1<<16);++i){
if(check(n,i)){
f[n][i]=1;
}
else f[n][i]=0;
}
for(int i=n-1;i>0;--i){
for(int j=0;j<(1<<16);++j){
if(check(i,j)){
f[i][j]=f[i+1][shl[j]]+f[i+1][shl[j]^1];
if(f[i][j]>1e18) f[i][j]=1e18+1;
}
else f[i][j]=0;
}
}
printf("Case #%d: ",++kase);
for(int i=1,j=0;i<=n;++i,j=shl[j]){
if(f[i][j]>=p){
printf("0");
}
else{
p-=f[i][j];
j^=1;
printf("1");
}
}
printf("\n");
}
return 0;
}
