题解 CF107C 【Arrangement】

更好的阅读体验：[点这里](https://www.cnblogs.com/acceptedzhs/p/13972263.html) 网上的题解大都不是很明白（注释都没有），我这里参考了一下这篇题解：[点这里](https://blog.csdn.net/alan_cty/article/details/78335605)，同时加入了很多注释方便大家理解。 首先，$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: ```cpp #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> 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<<n); //按辈分从老到年轻依次安排座位 for(int i=0;i<maxb;i++){ for(int j=0;j<=n;j++){ int y=cnt[i]+1; if(b[y]){//若辈分为cnt[i]+1的人已经安排了座位 //安排过的座位不满足这一个座位的要求，continue if((a[b[y]]&i)!=a[b[y]]) continue; //当前座位已经被占用了，也continue if((1<<(b[y]-1)&i)==(1<<b[y]-1)) continue; //如果辈分为cnt[i]+1的人刚好坐在x位置上，那么j=cnt[i]+1 if(b[y]==x) f[i|(1<<b[y]-1)][y]+=f[i][j]; //否则继续保持原来的j else f[i|(1<<b[y]-1)][j]+=f[i][j]; } else{ for(int k=1;k<=n;k++){//枚举辈分为cnt[y]+1的人应该放哪个位置 if(!(i&(1<<k-1))){ if((a[k]&i)!=a[k]) continue; //与上面类似的转移 if(k==x) f[i|(1<<k-1)][y]+=f[i][j]; else f[i|(1<<k-1)][j]+=f[i][j]; } } } } } } int main(){ scanf("%d%lld%d",&n,&year,&m);year-=2000; //cnt[i]表示i在二进制下1的个数 for(int i=1;i<BIT;i++) cnt[i]=cnt[i^(i&(-i))]+1; for(int i=1;i<=m;i++){ int x,y;scanf("%d%d",&x,&y); a[y]|=(1<<x-1); //a[i]是一个二进制数，其中1的位表示 这一位对应的 //座位上坐的人 的辈分 必须比 i座位上坐的人 的辈分 大 } for(int i=1;i<=n;i++){ solve(i);ll sum=0; for(int j=1;j<=n;j++){ if(!b[j]&&sum+f[(1<<n)-1][j]>=year){ //刚好加上这个位置坐辈分为j的人的方案数可以大过year b[j]=i;p[i]=j; year-=sum;break; } sum+=f[(1<<n)-1][j]; } if(!p[i]){//这一位无法确定，无解 puts("The times have changed"); return 0; } } for(int i=1;i<=n;i++) printf("%lld ",p[i]); puts(""); return 0; } ```