我天几百岁的教授

· · 题解

题面

题面

放个 CF 的 AC 记录。

思路

注意到 n \le 16 我们考虑状压 dp。

首先我们把每个约束看成一条边，那么约束存在矛盾就说明图中有环，这个可以使用拓扑排序。

我们把全合法排列按字典序排序，称首个合法排列为第 0 个。设 k=y-2001，那么我们需要求的就是第 k 个合法排列。

如何求第 k 个字典序排列？由于字典序优先按靠前的位置从小到大排序，所以对于每一位，我们从小到大枚举每个没被选择的数，这个数填在该位后剩下排列的可能数为 cnt，那么当 k < cnt 时，说明第 k 个字典序的排列在剩下的情况中，那么当前位置就是现在枚举的这个数；否则这个位置要填更大的数，那么现在的这些可能肯定在之后的排列之前，所以我们要把 k \gets k-cnt 再继续枚举。

所以现在我们需要处理的就是在有约束条件的情况下，求出某种填数后的排列数。因为 n 很小，可以考虑状压 dp 来计数。

因为所有的约束条件都是要求某个位置放置的数要比另一个位置的数小，所以我们应该从小到大枚举每个位置能放的数，同时我们就不用储存使用了哪些数字了。设 dp_{mask} 为在已经放的数的位置为状态 mask 时合法的排列数，那么该状态已经放的数就是 1 到该状态二进制中一的数量 。特别的，mask 为 0 时表示没放任何数。初始化 dp_0 为 1。

考虑转移。因为是从小到大枚举加入的数，所以填到某个位置时需要保证所有能直接到达这里的位置（即前驱）都被填入了数字。对于合法的转移，让目标状态加上当前状态的 dp 值就可以了。

我代码中多了的 low 和 upp 数组是因为我单独把没放数的位置拿了出来，而前驱只处理了空的位置之间的约束，所以还需要处理和已经放了数的位置的约束来限制一个位置能放的数的范围不过我不知道这个用处大不大。

代码

为了防止自己突然看不懂加了点注释。

#include <bits/stdc++.h>
using namespace std;
#define QwQ return
#define egg 0;
#define retrun return
#define int long long
#define iny unsigned long long
//  ? ? ?
// ?     ?
//?       ?
//?       ?
//       ?
//     ?
//    ?
//    ?
//
//    ?
constexpr int maxn=2e2+14;
constexpr int maxm=1e5+91;
constexpr int maxl=5e6+13;
constexpr double pi=acos(-1);
constexpr double eps=1e-7;
constexpr int mod=998244353;
constexpr int inf=LONG_LONG_MAX>>1;
constexpr double INF=1e12;

int n,y,m;
bool gra[18][18];
int val[18];
bool use[18];
int rd[18];
bool tuopu()
{
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(gra[i][j])
            {
                ++rd[j];
            }
        }
    }
    queue<int>q;
    for(int i=1;i<=n;++i)
    {
        if(!rd[i])
        {
            q.push(i);
        }
    }
    int cnt=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        ++cnt;
        for(int i=1;i<=n;++i)
        {
            if(gra[u][i])
            {
                if(!--rd[i])
                {
                    q.push(i);
                }
            }
        }
    }
    return cnt==n;
}
bool vis[18];
int count_(int mask,int v[])
{
    for(int i=1;i<=n;++i)
    {
        vis[i]=0;
    }
    vector<int>num;
    for(int i=1;i<=n;++i)
    {
        if(v[i])
        {
            vis[v[i]]=1;
        }
    }
    for(int i=1;i<=n;++i)
    {
        if(!vis[i])
        {
            num.push_back(i);
        }
    }
    int siz=num.size();
    vector<int>pos(n+1,-1);
    int idx=0;
    for(int i=1;i<=n;++i)
    {
        if(!(mask&(1<<(i-1))))//给每个未确定的座位分配一个连续的压缩索引（压缩空间）
        {
            pos[i]=idx++;
        }
    }
    vector<int>pre(siz,0);//所有没被使用的前驱位置的mask
    for(int i=1;i<=n;++i)
    {
        if(pos[i]==-1)//已确认的位置
        {
            continue;
        }
        for(int j=1;j<=n;++j)
        {
            if(gra[j][i]&&pos[j]!=-1)//val[j]<val[i]
            {
                pre[pos[i]]|=(1<<pos[j]);
            }
        }
    }
    vector<int>low(siz,0),upp(siz,siz-1);//每个位置可选数字的上下界
    bool o=1;
    for(int i=1;i<=n;++i)
    {
        if(pos[i]==-1)
        {
            continue;
        }
        int node=0;
        for(int j=1;j<=n;++j)
        {
            if(gra[j][i]&&v[j])//必须比所有前驱位置的值大
            {
                node=max(node,v[j]);
            }
        }
        low[pos[i]]=upper_bound(num.begin(),num.end(),node)-num.begin();//改为剩余数中的下标
        node=n+1;
        for(int j=1;j<=n;++j)
        {
            if(gra[i][j]&&v[j])//必须比所有后继位置的值小
            {
                node=min(node,v[j]);
            }
        }
        upp[pos[i]]=lower_bound(num.begin(),num.end(),node)-num.begin()-1;
        if(low[pos[i]]>upp[pos[i]])
        {
            o=0;
            break;
        }
    }
    if(!o)
    {
        return 0;
    }
    int up=1<<siz;
    vector<int>dp(up,0);
    dp[0]=1;
    for(int i=0;i<up;++i)
    {
        if(!dp[i])
        {
            continue;
        }
        int t=__builtin_popcountll(i);//现在放的数的num中的下标
        for(int j=0;j<siz;++j)
        {
            if(i&(1<<j))
            {
                continue;
            }
            if(t<low[j]||t>upp[j])
            {
                continue;
            }
            if((i&pre[j])!=pre[j])
            {
                continue;
            }
            dp[i|(1<<j)]+=dp[i];
        }
    }
    return dp[up-1];
}
signed main()
{
    scanf("%lld%lld%lld",&n,&y,&m);
    y-=2001;
    for(int i=1;i<=m;++i)
    {
        int a,b;
        scanf("%lld%lld",&a,&b);
        gra[a][b]=1;
    }
    if(!tuopu())
    {
        printf("The times have changed\n");
        QwQ egg
    }
    int mask=0;
    for(int i=1;i<=n;++i)
    {
        bool f=0;
        for(int x=1;x<=n;++x)
        {
            if(use[x])
            {
                continue;
            }
            bool o=1;
            for(int j=1;j<=n;++j)
            {
                if(!val[j])
                {
                    continue;
                }
                if(gra[i][j]&&x>=val[j])
                {
                    o=0;
                    break;
                }
                if(gra[j][i]&&val[j]>=x)
                {
                    o=0;
                    break;
                }
            }
            if(!o)
            {
                continue;
            }
            val[i]=x;
            use[x]=1;
            mask|=(1<<(i-1));
            int cnt=count_(mask,val);
            if(y<cnt)
            {
                f=1;
                break;
            }
            else
            {
                y-=cnt;
                val[i]=0;
                use[x]=0;
                mask^=(1<<(i-1));
            }
        }
        if(!f)
        {
            printf("The times have changed\n");
            QwQ egg
        }
    }
    for(int i=1;i<=n;++i)
    {
        printf("%lld ",val[i]);
    }
    printf("\n");
    /*
    //I often die
    //I often die
    //I often die
    //I often die
    //I often die
    //I often die
    //I often die
    //I often die
    //I always die */
    QwQ egg
}