CF107C Arrangement 题解

网上的题解大都不是很明白（注释都没有），我这里参考了一下这篇题解：alan_cty - csdn 博客，同时加入了很多注释方便大家理解。

首先，\(n\) 很小，容易想到状压。

我们可以依次确定排列中每一位应该坐哪个人。那么，我们只需要知道某一位选辈分为\(j\)的人的方案数。

设\(f_{i,j}\)表示当前状态的方案数，其中\(i\)是一个二进制数，值为\(1\)的位表示对应的座位已经安排给了辈分为\(1 \sim cnt_i\)的人（\(1\)为最老，\(cnt_i\)表示\(i\)在二进制下\(1\)的位数），\(j\)表示第\(x\)个座位确定由辈分为\(j\)的人来坐。

最终结果是\(f_{{2^n-1},y}\)，\(y \in [1,n]\)。

如何转移呢？我们可以枚举辈分\(cnt_i+1\)的人坐哪个位置，进行转移即可。（具体见代码中的注释）

Code:

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int BIT=(1<<17),M=110,N=25;
int n,m,cnt[BIT],a[M];
ll f[BIT][N],b[N],p[N],year;
//f[i][j]
//i中1的位表示对应的座位已经安排给了辈分为1~cnt[i]的人(1为最老)
//j表示第x位确定安排给辈分为j的人坐
//b[i]表示辈分为i的人在哪个位置

//辈分为1~n，1为最老，n为最年轻
void solve(int x){
    memset(f,0,sizeof(f));
    f[0][0]=1;int maxb=(1<=year){
                //刚好加上这个位置坐辈分为j的人的方案数可以大过year
                b[j]=i;p[i]=j;
                year-=sum;break;
            }
            sum+=f[(1<